%!PS
%%Version: 3.3
%%DocumentFonts: (atend)
%%Pages: (atend)
%%EndComments
%
% Version 3.3 prologue for troff files.
%

/#copies 1 store
/aspectratio 1 def
/formsperpage 1 def
/landscape false def
/linewidth .3 def
/magnification 1 def
/margin 0 def
/orientation 0 def
/resolution 720 def
/rotation 1 def
/xoffset 0 def
/yoffset 0 def

/roundpage true def
/useclippath true def
/pagebbox [0 0 612 792] def

/R  /Times-Roman def
/I  /Times-Italic def
/B  /Times-Bold def
/BI /Times-BoldItalic def
/H  /Helvetica def
/HI /Helvetica-Oblique def
/HB /Helvetica-Bold def
/HX /Helvetica-BoldOblique def
/CW /Courier def
/CO /Courier def
/CI /Courier-Oblique def
/CB /Courier-Bold def
/CX /Courier-BoldOblique def
/PA /Palatino-Roman def
/PI /Palatino-Italic def
/PB /Palatino-Bold def
/PX /Palatino-BoldItalic def
/Hr /Helvetica-Narrow def
/Hi /Helvetica-Narrow-Oblique def
/Hb /Helvetica-Narrow-Bold def
/Hx /Helvetica-Narrow-BoldOblique def
/KR /Bookman-Light def
/KI /Bookman-LightItalic def
/KB /Bookman-Demi def
/KX /Bookman-DemiItalic def
/AR /AvantGarde-Book def
/AI /AvantGarde-BookOblique def
/AB /AvantGarde-Demi def
/AX /AvantGarde-DemiOblique def
/NR /NewCenturySchlbk-Roman def
/NI /NewCenturySchlbk-Italic def
/NB /NewCenturySchlbk-Bold def
/NX /NewCenturySchlbk-BoldItalic def
/ZD /ZapfDingbats def
/ZI /ZapfChancery-MediumItalic def
/S  /S def
/S1 /S1 def
/GR /Symbol def

/inch {72 mul} bind def
/min {2 copy gt {exch} if pop} bind def

/setup {
	counttomark 2 idiv {def} repeat pop

	landscape {/orientation 90 orientation add def} if
	/scaling 72 resolution div def
	linewidth setlinewidth
	1 setlinecap

	pagedimensions
	xcenter ycenter translate
	orientation rotation mul rotate
	width 2 div neg height 2 div translate
	xoffset inch yoffset inch neg translate
	margin 2 div dup neg translate
	magnification dup aspectratio mul scale
	scaling scaling scale

	/Symbol /S Sdefs cf
	/Times-Roman /S1 S1defs cf
	0 0 moveto
} def

/pagedimensions {
	useclippath userdict /gotpagebbox known not and {
		/pagebbox [clippath pathbbox newpath] def
		roundpage currentdict /roundpagebbox known and {roundpagebbox} if
	} if
	pagebbox aload pop
	4 -1 roll exch 4 1 roll 4 copy
	landscape {4 2 roll} if
	sub /width exch def
	sub /height exch def
	add 2 div /xcenter exch def
	add 2 div /ycenter exch def
	userdict /gotpagebbox true put
} def

/pagesetup {
	/page exch def
	currentdict /pagedict known currentdict page known and {
		page load pagedict exch get cvx exec
	} if
} def

/decodingdefs [
	{counttomark 2 idiv {y moveto show} repeat}
	{neg /y exch def counttomark 2 idiv {y moveto show} repeat}
	{neg moveto {2 index stringwidth pop sub exch div 0 32 4 -1 roll widthshow} repeat}
	{neg moveto {spacewidth sub 0.0 32 4 -1 roll widthshow} repeat}
	{counttomark 2 idiv {y moveto show} repeat}
	{neg setfunnytext}
] def

/setdecoding {/t decodingdefs 3 -1 roll get bind def} bind def

/w {neg moveto show} bind def
/m {neg dup /y exch def moveto} bind def
/done {/lastpage where {pop lastpage} if} def

/f {
	dup /font exch def findfont exch
	dup /ptsize exch def scaling div dup /size exch def scalefont setfont
	linewidth ptsize mul scaling 10 mul div setlinewidth
	/spacewidth ( ) stringwidth pop def
} bind def

/changefont {
	/fontheight exch def
	/fontslant exch def
	currentfont [
		1 0
		fontheight ptsize div fontslant sin mul fontslant cos div
		fontheight ptsize div
		0 0
	] makefont setfont
} bind def

/sf {f} bind def

/cf {
	dup length 2 idiv
	/entries exch def
	/chtab exch def
	/newfont exch def

	findfont dup length 1 add dict
	/newdict exch def
	{1 index /FID ne {newdict 3 1 roll put} {pop pop} ifelse} forall

	newdict /Metrics entries dict put
	newdict /Metrics get
	begin
		chtab aload pop
		1 1 entries {pop def} for
		newfont newdict definefont pop
	end
} bind def

%
% A few arrays used to adjust reference points and character widths in some
% of the printer resident fonts. If square roots are too high try changing
% the lines describing /radical and /radicalex to,
%
%	/radical	[0 -75 550 0]
%	/radicalex	[-50 -75 500 0]
%
% Move braceleftbt a bit - default PostScript character is off a bit.
%

/Sdefs [
	/bracketlefttp		[201 500]
	/bracketleftbt		[201 500]
	/bracketrighttp		[-81 380]
	/bracketrightbt		[-83 380]
	/braceleftbt		[203 490]
	/bracketrightex		[220 -125 500 0]
	/radical		[0 0 550 0]
	/radicalex		[-50 0 500 0]
	/parenleftex		[-20 -170 0 0]
	/integral		[100 -50 500 0]
	/infinity		[10 -75 730 0]
] def

/S1defs [
	/underscore		[0 80 500 0]
	/endash			[7 90 650 0]
] def
%%EndProlog
%%BeginSetup
mark
/resolution 720 def
setup
2 setdecoding
%%EndSetup
%%Page: 1 1
/saveobj save def
mark
1 pagesetup
16 B f
(Parallel Sorting by Regular Sampling)4 2574 1 1553 860 t
16 R f
(\262)4127 860 w
12 I f
(Hanmao Shi)1 596 1 2582 1280 t
(Jonathan Schaeffer)1 931 1 2414 1560 t
12 R f
(Department of Computing Science)3 1672 1 2044 1980 t
(University of Alberta)2 1028 1 2366 2260 t
(Edmonton, Alberta)1 921 1 2419 2540 t
(Canada T6G 2H1)2 844 1 2458 2820 t
(jonathan@cs.UAlberta.CA)2232 3240 w
10 S1 f
(_ ______________)1 720 1 720 6820 t
10 R f
( research was provided by the Canadian Natural Sciences and Engineering)10 3180(\262 Funding for this)3 780 2 720 6940 t
(Resewrch Council, grant number OGP-8173.)4 1803 1 720 7060 t
cleartomark
showpage
saveobj restore
%%EndPage: 1 1
%%Page: 2 2
/saveobj save def
mark
2 pagesetup
12 R f
(- 2 -)2 200 1 2780 500 t
(Running head: "Parallel Sorting by Regular Sampling")6 2637 1 720 860 t
(Contact author:)1 745 1 720 1560 t
(Jonathan Schaeffer)1 916 1 1440 1980 t
(Department of Computing Science)3 1672 1 1440 2120 t
(University of Alberta)2 1028 1 1440 2260 t
(Edmonton, Alberta)1 921 1 1440 2400 t
(Canada T6G 2H1)2 844 1 1440 2540 t
(W: 403-492-3851)1 857 1 1440 2820 t
(H: 403-464-0740)1 830 1 1440 2960 t
(F: 403-492-1071)1 811 1 1440 3100 t
cleartomark
showpage
saveobj restore
%%EndPage: 2 2
%%Page: 3 3
/saveobj save def
mark
3 pagesetup
12 R f
(- 3 -)2 200 1 2780 500 t
12 B f
(ABSTRACT)2554 860 w
12 R f
( suitable for MIMD multiprocessors is)5 2074(A new parallel sorting algorithm)4 1746 2 970 1176 t
( many)1 315( algorithm reduces memory and bus contention, which)7 2750(presented. The)1 755 3 970 1456 t
( from, by using a)4 826(parallel sorting algorithms suffer)3 1585 2 970 1736 t
12 I f
(regular sampling)1 834 1 3413 1736 t
12 R f
(of the data)2 511 1 4279 1736 t
( For)1 233(to ensure good pivot selection.)4 1497 2 970 2016 t
12 I f
(n)2735 2016 w
12 R f
(data elements to be sorted and)5 1477 1 2830 2016 t
12 I f
(p)4342 2016 w
12 R f
(proces-)4437 2016 w
(sors, when)1 530 1 970 2296 t
12 I f
(n)1547 2296 w
12 S f
(\263)1657 2296 w
12 I f
(p)1773 2296 w
9 R f
(3)1848 2248 w
12 R f
( In)1 178(the algorithm is shown to be asymptotically optimal.)7 2662 2 1950 2296 t
( ideal load balanc-)3 908(theory, the algorithm is within a factor of two of achieving)10 2912 2 970 2576 t
( a variety of)3 607( On)1 216( there is almost perfect partitioning of work.)7 2195( practice,)1 449(ing. In)1 353 5 970 2856 t
(shared and distributed memory machines, the algorithm achieves better than)9 3820 1 970 3136 t
(half-linear speedups.)1 1001 1 970 3416 t
cleartomark
showpage
saveobj restore
%%EndPage: 3 3
%%Page: 4 4
/saveobj save def
mark
4 pagesetup
12 R f
(- 4 -)2 200 1 2780 500 t
12 B f
(1. Introduction)1 805 1 720 860 t
12 R f
( of most studied problems in computer science because of its theoreti-)11 3397(Sorting is one)2 673 2 970 1176 t
( the advent of parallel processing, parallel)6 2139( With)1 322( practical importance.)2 1087(cal interest and)2 772 4 720 1456 t
( considerable)1 662( Although)1 539(sorting has become an important area for algorithm research.)8 3119 3 720 1736 t
( done on the theory of parallel sorting and efficient implementations on)11 3596(work has been)2 724 2 720 2016 t
( on a variety of multiprocessor MIMD)6 1969(SIMD architectures, good parallel performance)4 2351 2 720 2296 t
(architectures with a large number of processors remains a challenging problem.)10 3821 1 720 2576 t
( pro-)1 248( Akl)1 258( algorithms have been proposed.)4 1630(A multitude of innovative parallel sort)5 1934 4 970 2892 t
( is not practical to mention all previous pro-)8 2169( It)1 141(vides a good overview of the subject [2].)7 2010 3 720 3172 t
( there a necessity to do so, since)7 1570( is)1 114( Nor)1 249(posed parallel sorts here due to space limitations.)7 2387 4 720 3452 t
( them are based on unrealistic assumptions, which are beyond our interests.)11 3897(many of)1 423 2 720 3732 t
( algorithms that we consider representative of work in this area are dis-)12 3562(Instead, several)1 758 2 720 4012 t
( to yield good)3 713( algorithms are characterized by being realistic and likely)8 2894(cussed. These)1 713 3 720 4292 t
(performance in an implementation.)3 1690 1 720 4572 t
( achievable on a multiprocessor depends largely on)7 2571(The speedup of a parallel sort)5 1499 2 970 4888 t
( latency and overhead of scheduling and synchronization)7 2815(how well the average memory)4 1505 2 720 5168 t
( sorts suitable)2 689( on the general strategies utilized, most parallel)7 2357( Based)1 365(can be minimized.)2 909 4 720 5448 t
( computers can be placed into one of two rough categories: merge-)11 3414(for multiprocessor)1 906 2 720 5728 t
( sorts consist of multiple merge stages)6 1852( Merge-based)1 688( partition-based sorts.)2 1044(based sorts and)2 736 4 720 6008 t
( the)1 185( When)1 355(across processors, and perform well only with a small number of processors.)11 3780 3 720 6288 t
( so does the overhead of scheduling and syn-)8 2290(number of processors utilized gets large,)5 2030 2 720 6568 t
( sorts consist of two phases:)5 1447( Partition-based)1 809(chronization, which reduces the speedup.)4 2064 3 720 6848 t
( no)1 161(partitioning the data set into smaller subsets such that all elements in one subset are)14 4159 2 720 7128 t
cleartomark
showpage
saveobj restore
%%EndPage: 4 4
%%Page: 5 5
/saveobj save def
mark
5 pagesetup
12 R f
(- 5 -)2 200 1 2780 500 t
( performance)1 637( The)1 247( another, and sorting each subset in parallel.)7 2120(greater than any element in)4 1316 4 720 860 t
( primarily depends on how well the data can be evenly partitioned)11 3206(of partition-based sorts)2 1114 2 720 1140 t
( no general, effective method is currently)6 2099( Unfortunately,)1 784(into smaller ordered subsets.)3 1437 3 720 1420 t
( sorting)1 370(available, and it is an open question of how to achieve linear speedup for parallel)14 3950 2 720 1700 t
(on multiprocessors with a large number of processors.)7 2604 1 720 1980 t
( basic result)2 581( The)1 249( 8, 17].)2 320( research [6,)2 595(Parallel Quicksort has been a popular choice for)7 2325 5 970 2296 t
( limits the speedup to a maximum, generally believed to be)10 2994(is that initial data splitting)4 1326 2 720 2576 t
( similar effect happens to)4 1264( A)1 158( 6, regardless of how many processors are used.)8 2389(about 5 or)2 509 4 720 2856 t
(Evans and Yousif's two-way, merged-based parallel sort [9], as little parallelism can be)12 4320 1 720 3136 t
( and Mathieson have noticed this prob-)6 1894( Francis)1 416(exploited in the last few phases of merge.)7 2010 3 720 3416 t
( which evenly partitions data to be merged)7 2081(lem and proposed a parallel Mergesort \(PMS\))6 2239 2 720 3696 t
( this sorting algorithm is merge-based)5 1878( However,)1 538(among any number of processors [10].)5 1904 3 720 3976 t
( too much data movement, causing frequent memory refer-)8 2953(and, consequently, involves)2 1367 2 720 4256 t
( has implemented a combination of)5 1814( Quinn)1 384( and serious bus contention.)4 1435(ence conflicts)1 687 4 720 4536 t
( data move-)2 583(Quicksort and Mergesort, Quickmerge, significantly reducing the amount of)8 3737 2 720 4816 t
( is unstable in the sense that the pivots \(or divid-)10 2404( its execution time)3 905( However)1 504(ment [18].)1 507 4 720 5096 t
( into ordered subsets rea-)4 1244(ers\) selected are not guaranteed to divide the data to be sorted)11 3076 2 720 5376 t
( single processor may have to perform a Mergesort)8 2529( the worst case, a)4 859( In)1 169(sonably evenly.)1 763 4 720 5656 t
(on nearly all the data in the last phase, which makes linear speedup impossible.)13 3810 1 720 5936 t
( is essential for)3 855(The ability to partition the data evenly into ordered subsets)9 3215 2 970 6252 t
( statistics of the data are known, it becomes easy)9 2382( the distribution)2 776( If)1 146(partition-based sorts.)1 1016 4 720 6532 t
( the data into equal-sized subsets such that each element in the)11 3101(to divide)1 433 2 720 6812 t
12 I f
(i)4293 6812 w
12 R f
(th subset is no)3 713 1 4327 6812 t
(greater than any element in the \()6 1669 1 720 7092 t
12 I f
(i)2399 7092 w
12 S f
(+)2463 7092 w
12 R f
( in parallel.)2 581( subset, and then sort each subset)6 1706(1 \)th)1 204 3 2549 7092 t
cleartomark
showpage
saveobj restore
%%EndPage: 5 5
%%Page: 6 6
/saveobj save def
mark
6 pagesetup
12 R f
(- 6 -)2 200 1 2780 500 t
( overcome this diffi-)3 1004( To)1 199( general, we do not know the data distribution.)8 2284(Unfortunately, in)1 833 4 720 860 t
( data and use the)4 828(culty, Huang and Chow proposed extracting a random sample from the)10 3492 2 720 1140 t
(order information of the sample to help the partitioning, Parallel Sorting by Sampling)12 4320 1 720 1420 t
( of the ori-)3 523( effectiveness of sampling depends largely on the distribution)8 3000( The)1 251(\(PSS\) [12].)1 546 4 720 1700 t
(ginal data, the choice of a proper sample size, and the way in which the sample is drawn.)17 4320 1 720 1980 t
( that partition the data to be sorted into)8 1914(It appears to be a difficult problem to find pivots)9 2406 2 720 2260 t
(ordered subsets of equal size without sorting the data first.)9 2806 1 720 2540 t
( of mul-)2 406(This paper describes a new parallel sorting algorithm suitable for a variety)11 3664 2 970 2856 t
(tiprocessor architectures.)1 1212 1 720 3136 t
12 I f
(Parallel Sorting by Regular Sampling \(PSRS\))5 2245 1 2002 3136 t
12 R f
(finds pivots for)2 754 1 4286 3136 t
( using a)2 388(partitioning the data into ordered subsets of approximately equal size by)10 3534 2 720 3416 t
12 I f
(regular)4679 3416 w
(sample)720 3696 w
12 R f
( that this form of sampling results in)7 1779( is proven)2 484( It)1 139(from sorted sublists of the data.)5 1543 4 1095 3696 t
( practice,)1 443( In)1 163( a factor of two of achieving ideal load balancing.)9 2415(all processors being within)3 1299 4 720 3976 t
( of shared and distri-)4 1015( a variety)2 459( On)1 212(this results in a nearly perfect partitioning of the data.)9 2634 4 720 4256 t
(buted memory machines, including the Myrias SPS-2, BBN TC2000, a local area net-)12 4320 1 720 4536 t
( algorithm)1 499(work of Sun 3/80 workstations, and iPSC/2-386 and iPSC/860 Hypercubes, the)10 3821 2 720 4816 t
( 8,000,000)1 518( example, on the SPS-2, sorting)5 1555( For)1 234(achieves better than half-linear speedups.)4 2013 4 720 5096 t
(data items on 64 processors achieved a 44.4-fold speedup.)8 2795 1 720 5376 t
12 B f
( Sorting by Regular Sampling)4 1530(2. Parallel)1 551 2 720 5796 t
12 R f
( on a)2 249(Let the data set to be sorted)6 1364 2 970 6112 t
12 I f
(p)2621 6112 w
12 R f
(-processor MIMD multiprocessor be denoted by)5 2359 1 2681 6112 t
12 I f
(X)720 6392 w
12 R f
(, and the size of)4 809 1 793 6392 t
12 I f
(X)1645 6392 w
12 R f
(be)1761 6392 w
12 I f
(n)1916 6392 w
12 R f
(. Let)1 262 1 1976 6392 t
12 I f
(X)2280 6392 w
9 I f
(i)2368 6416 w
9 R f
(:)2400 6416 w
9 I f
(j)2440 6416 w
12 R f
(be {)1 213 1 2517 6392 t
12 I f
(X)2772 6392 w
9 I f
(i)2860 6416 w
12 R f
(,)2895 6392 w
12 I f
(X)2967 6392 w
9 I f
(i)3055 6416 w
9 S f
(+)3102 6416 w
9 R f
(1)3167 6416 w
12 R f
(, ...)1 162 1 3222 6392 t
12 I f
(X)3426 6392 w
9 I f
(j)3514 6416 w
12 R f
(}, where 0)2 524 1 3591 6392 t
12 S f
(\243)4165 6392 w
12 I f
(i)4281 6392 w
12 S f
(\243)4365 6392 w
12 I f
(j)4491 6392 w
12 S f
(<)4585 6392 w
12 I f
(n)4711 6392 w
12 R f
(. For)1 269 1 4771 6392 t
(simplicity in the analysis of the algorithm, we assume)8 2592 1 720 6672 t
12 I f
(p)3342 6672 w
9 R f
(2)3417 6624 w
12 S f
(\357)3502 6672 w
12 I f
(n)3591 6672 w
12 R f
(and)3681 6672 w
12 I f
(X)3884 6672 w
9 I f
(i)3972 6696 w
12 S f
(\271)4057 6672 w
12 I f
(X)4173 6672 w
9 I f
(j)4261 6696 w
12 R f
(, where)1 352 1 4296 6672 t
12 I f
(i)4678 6672 w
12 S f
(\271)4762 6672 w
12 I f
(j)4888 6672 w
12 R f
(.)4922 6672 w
( appendix outlines the pseudo-code for the algorithm)7 2646( The)1 261(PSRS has three phases.)3 1163 3 970 6988 t
( the first phase, each of)5 1229( In)1 183( [22]\).)1 323(\(more details can be found in)5 1525 4 720 7268 t
12 I f
(p)4033 7268 w
12 R f
(processors sorts a)2 894 1 4146 7268 t
cleartomark
showpage
saveobj restore
%%EndPage: 6 6
%%Page: 7 7
/saveobj save def
mark
7 pagesetup
12 R f
(- 7 -)2 200 1 2780 500 t
(contiguous list of size)3 1069 1 720 908 t
12 I f
(w)1824 908 w
12 S f
(=)1964 908 w
12 I f
(p)2120 992 w
(n)2120 836 w
12 S1 f
(_ _)1 96 1 2102 872 t
12 R f
( precisely, each proces-)3 1144( More)1 326(using sequential Quicksort.)2 1325 3 2245 908 t
(sor)720 1248 w
12 I f
(i)904 1248 w
12 R f
(\(1)975 1248 w
12 S f
(\243)1125 1248 w
12 I f
(i)1241 1248 w
12 S f
(\243)1325 1248 w
12 I f
(p)1441 1248 w
12 R f
(\) sorts a list)3 581 1 1501 1248 t
12 I f
(X)2119 1248 w
9 R f
(\()2207 1272 w
9 I f
(i)2244 1272 w
9 S f
(-)2291 1272 w
9 R f
(1 \))1 82 1 2356 1272 t
9 I f
(w)2453 1272 w
9 R f
(:)2550 1272 w
9 I f
(iw)2612 1272 w
9 S f
(-)2742 1272 w
9 R f
(1)2807 1272 w
12 R f
( this phase all proces-)4 1066( After)1 320(with Quicksort.)1 755 3 2899 1248 t
(sors synchronize and)2 1009 1 720 1528 t
12 I f
(X)1760 1528 w
12 R f
( of)1 132( is convenient to think)4 1074( It)1 135(is now said to be locally ordered.)6 1598 4 1864 1528 t
12 I f
(X)4835 1528 w
12 R f
(as)4940 1528 w
( containing)1 539(one contiguous list)2 914 2 720 1808 t
12 I f
(p)2204 1808 w
12 R f
( practice, depending on the architecture,)5 1929( In)1 161(sorted lists.)1 551 3 2295 1808 t
12 I f
(X)4967 1808 w
12 R f
(may in fact be distributed over the processors.)7 2217 1 720 2088 t
(Define the)1 534 1 970 2404 t
12 I f
(regular sample)1 763 1 1566 2404 t
12 R f
(of the locally ordered)3 1127 1 2391 2404 t
12 I f
(X)3580 2404 w
12 R f
(be a set of the following)5 1325 1 3715 2404 t
12 I f
(p)720 2684 w
12 R f
(\()790 2684 w
12 I f
(p)840 2684 w
12 S f
(-)960 2684 w
12 R f
( elements:)1 492(1 \))1 110 2 1086 2684 t
12 I f
(X)1207 3034 w
9 I f
(p)1332 3121 w
(w)1325 3004 w
9 S1 f
(_ __)1 102 1 1304 3031 t
9 S f
(+)1437 3058 w
9 I f
(j w)1 92 1 1502 3058 t
12 R f
(,)1614 3034 w
12 I f
(X)1734 3034 w
9 I f
(p)1885 3121 w
9 R f
(2)1852 3004 w
9 I f
(w)1904 3004 w
9 S1 f
(_ ___)1 154 1 1831 3031 t
9 S f
(+)2016 3058 w
9 I f
(j w)1 92 1 2081 3058 t
12 R f
(,)2193 3034 w
12 I f
(.)2313 3034 w
12 R f
(.. ,)1 100 1 2343 3034 t
12 I f
(X)2533 3034 w
9 I f
(p)2791 3121 w
9 R f
(\()2651 3004 w
9 I f
(p)2688 3004 w
9 S f
(-)2755 3004 w
9 R f
(1 \))1 82 1 2820 3004 t
9 I f
(w)2917 3004 w
9 S1 f
(_ ________)1 368 1 2630 3031 t
9 S f
(+)3029 3058 w
9 I f
(j w)1 92 1 3094 3058 t
12 R f
(, Rwhere)1 502 1 3206 3034 t
12 I f
(P)3728 3034 w
12 R f
(0)3851 3034 w
12 S f
(\243)3961 3034 w
12 I f
(j)4087 3034 w
12 S f
(\243)4171 3034 w
12 I f
(p)4287 3034 w
12 S f
(-)4377 3034 w
12 R f
(1.)4463 3034 w
(From each of the)3 817 1 720 3343 t
12 I f
(p)1567 3343 w
12 R f
(lists,)1657 3343 w
12 I f
(p)1913 3343 w
12 S f
(-)2003 3343 w
12 R f
( The)1 247( are chosen, evenly spaced throughout the list.)7 2226(1 samples)1 478 3 2089 3343 t
( pivots,)1 378( The)1 269( data set.)2 470(regular sample contains the "order information" of the original)8 3203 4 720 3623 t
( size, will also)3 719(which divides the regular sample into ordered subsets of sample of equal)11 3601 2 720 3903 t
(partition the original data into order subsets of roughly equal size.)10 3171 1 720 4183 t
(In the second phase, the regular sample set,)7 2141 1 970 4499 t
12 I f
(Y)3150 4499 w
12 R f
(, is sorted using sequential Quicksort)5 1823 1 3217 4499 t
( ordered list)2 583(yielding an)1 543 2 720 4779 t
12 I f
(Y)1880 4779 w
9 R f
(1)1962 4803 w
12 R f
(,)2027 4779 w
12 I f
(Y)2107 4779 w
9 R f
(2)2189 4803 w
12 R f
(,)2254 4779 w
12 I f
(.)2334 4779 w
12 R f
(.. ,)1 100 1 2364 4779 t
12 I f
(Y)2514 4779 w
9 I f
(p)2596 4803 w
9 R f
(\()2648 4803 w
9 I f
(p)2685 4803 w
9 S f
(-)2752 4803 w
9 R f
(1 \))1 82 1 2817 4803 t
12 R f
( choose)1 367(. Next)1 327 2 2909 4779 t
12 I f
(Y)3637 4779 w
9 R f
(2)3749 4866 w
9 I f
(p)3749 4749 w
9 S1 f
(_ _)1 87 1 3728 4776 t
12 R f
(,)3834 4779 w
12 I f
(Y)3898 4779 w
9 I f
(p)3980 4803 w
9 S f
(+)4047 4803 w
9 R f
(2)4142 4866 w
9 I f
(p)4142 4749 w
9 S1 f
(_ _)1 87 1 4121 4776 t
12 R f
(, ...,)1 184 1 4227 4779 t
12 I f
(Y)4445 4779 w
9 R f
(\()4527 4803 w
9 I f
(p)4564 4803 w
9 S f
(-)4631 4803 w
9 R f
(2 \))1 82 1 4696 4803 t
9 I f
(p)4793 4803 w
9 S f
(+)4860 4803 w
9 R f
(2)4955 4866 w
9 I f
(p)4955 4749 w
9 S1 f
(_ _)1 87 1 4934 4776 t
12 R f
(as the)1 278 1 720 5122 t
12 I f
(p)1029 5122 w
12 S f
(-)1119 5122 w
12 R f
( for partitioning)2 767(1 pivots)1 386 2 1205 5122 t
12 I f
(X)2390 5122 w
12 R f
(, referred to as)3 699 1 2463 5122 t
12 I f
(y)3194 5122 w
9 R f
(1 ,)1 75 1 3262 5146 t
12 I f
(y)3397 5122 w
9 R f
(2 ,)1 75 1 3465 5146 t
12 I f
(.)3600 5122 w
12 R f
(.. ,)1 100 1 3630 5122 t
12 I f
(y)3780 5122 w
9 I f
(p)3848 5146 w
9 S f
(-)3915 5146 w
9 R f
(1)3980 5146 w
12 R f
( other words, the)3 813(. In)1 192 2 4035 5122 t
12 I f
(p)720 5402 w
12 R f
(\()790 5402 w
12 I f
(p)840 5402 w
12 S f
(-)960 5402 w
12 R f
( sorted and)2 551( samples are)2 620(1 \))1 110 3 1086 5402 t
12 I f
(p)2409 5402 w
12 S f
(-)2529 5402 w
12 R f
(1 elements, evenly spaced throughout the sorted)6 2385 1 2655 5402 t
(list, are chosen to be the pivots.)6 1517 1 720 5682 t
(The partitioning of)2 921 1 970 5998 t
12 I f
(X)1927 5998 w
12 R f
( where each)2 585( processor finds)2 773( Each)1 305(is accomplished as follows.)3 1341 4 2036 5998 t
(of the)1 279 1 720 6278 t
12 I f
(p)1031 6278 w
12 S f
(-)1121 6278 w
12 R f
( precisely, each processor)3 1236( More)1 322(1 pivots divides its list, using a binary search.)8 2210 3 1207 6278 t
12 I f
(i)5006 6278 w
12 R f
(\(1)720 6558 w
12 S f
(\243)870 6558 w
12 I f
(i)986 6558 w
12 S f
(\243)1070 6558 w
12 I f
(p)1186 6558 w
12 R f
(\) finds the index of the largest element no larger than the)11 3201 1 1246 6558 t
12 I f
(j)4520 6558 w
12 R f
(-th pivot,)1 486 1 4554 6558 t
12 I f
(j)720 6838 w
12 S f
(=)814 6838 w
12 R f
( ,)1 40( 2)1 110(1 ,)1 100 3 940 6838 t
12 I f
(.)1240 6838 w
12 R f
(.. ,)1 100 1 1270 6838 t
12 I f
(p)1420 6838 w
12 S f
(-)1510 6838 w
12 R f
( this point each of)4 910( At)1 192( doing this, all processors synchronize.)5 1927(1. After)1 415 4 1596 6838 t
(the)720 7118 w
12 I f
(p)897 7118 w
12 R f
(sorted lists of)2 650 1 987 7118 t
12 I f
(X)1667 7118 w
12 R f
(have been divided into)3 1091 1 1770 7118 t
12 I f
(p)2891 7118 w
12 R f
(sorted sublists with the property that every)6 2058 1 2982 7118 t
cleartomark
showpage
saveobj restore
%%EndPage: 7 7
%%Page: 8 8
/saveobj save def
mark
8 pagesetup
12 R f
(- 8 -)2 200 1 2780 500 t
( every list's)2 562(item in)1 340 2 720 860 t
12 I f
(i)1652 860 w
12 R f
(-th sorted sublist is greater than any item in any list's \()11 2626 1 1686 860 t
12 I f
(i)4322 860 w
12 S f
(-)4386 860 w
12 R f
( sorted)1 324(1 \)-th)1 244 2 4472 860 t
(sublist, for 2)2 606 1 720 1140 t
12 S f
(\243)1376 1140 w
12 I f
(i)1492 1140 w
12 S f
(\243)1576 1140 w
12 I f
(p)1692 1140 w
12 R f
(.)1752 1140 w
( processor)1 491(In the last phase, each)4 1057 2 970 1456 t
12 I f
(i)2549 1456 w
12 R f
(\(1)2614 1456 w
12 S f
(\243)2764 1456 w
12 I f
(i)2880 1456 w
12 S f
(\243)2964 1456 w
12 I f
(p)3080 1456 w
12 R f
(\) performs a)2 589 1 3140 1456 t
12 I f
(p)3760 1456 w
12 R f
(-way Mergesort to merge)3 1220 1 3820 1456 t
(all the)1 303 1 720 1736 t
12 I f
(i)1058 1736 w
12 R f
(-th sorted sublists of)3 996 1 1092 1736 t
12 I f
(p)2123 1736 w
12 R f
( phase one, in which each processor)6 1746( that unlike)2 552(lists. Note)1 524 3 2218 1736 t
(sorts a contiguous block of keys, in phase three each processor merges)11 3389 1 720 2016 t
12 I f
(p)4139 2016 w
12 R f
(sublists stored in)2 811 1 4229 2016 t
12 I f
(p)720 2296 w
12 R f
( merges are)2 557( of the demarcations established in phase two, their)8 2485( Because)1 462(different areas.)1 723 4 813 2296 t
( this all processors synchronize and)5 1811( After)1 334( other.)1 328(completely independent of each)3 1591 4 720 2576 t
12 I f
(X)4835 2576 w
12 R f
(is)4959 2576 w
(sorted.)720 2856 w
( illustrates how PSRS works for)5 1565(Fig. 1)1 285 2 970 3172 t
12 I f
(n)2855 3172 w
12 S f
(=)2975 3172 w
12 R f
(36 and)1 328 1 3101 3172 t
12 I f
(p)3464 3172 w
12 S f
(=)3584 3172 w
12 R f
( phase 1, each proces-)4 1075(3. In)1 255 2 3710 3172 t
(sor is assigned)2 704 1 720 3500 t
12 I f
(w)1455 3500 w
12 S f
(=)1595 3500 w
12 I f
(p)1751 3584 w
(n)1751 3428 w
12 S1 f
(_ _)1 96 1 1733 3464 t
12 S f
(=)1901 3500 w
12 R f
( sorting its list, each pro-)5 1198( After)1 313( elements to sort.)3 823(12 contiguous)1 679 4 2027 3500 t
( the 12 ele-)3 570(cessor selects a regular sample, elements 4 and 8, evenly spaced throughout)11 3750 2 720 3840 t
( the)1 185( the second phase,)3 900(ments. In)1 487 3 720 4120 t
12 I f
(p)2330 4120 w
12 R f
(\()2400 4120 w
12 I f
(p)2450 4120 w
12 S f
(-)2570 4120 w
12 R f
( In)1 168( samples are gathered together and sorted.)6 2066(1 \))1 110 3 2696 4120 t
( this, a regular)3 733( From)1 335(the example, this is the list of elements {10, 13, 16, 22, 23, 27}.)13 3252 3 720 4400 t
(sample of)1 479 1 720 4680 t
12 I f
(p)1237 4680 w
12 S f
(-)1357 4680 w
12 R f
(1)1483 4680 w
12 S f
(=)1603 4680 w
12 R f
( list, resulting in)3 806(2 pivots are selected, evenly spaced throughout the)7 2505 2 1729 4680 t
(the selection of pivots 14 and 23.)6 1593 1 720 4960 t
( the pivots.)2 538(Finally, the 3 sorted lists of 12 elements are partitioned into 3 sublists by)13 3532 2 970 5276 t
( others on to the appropriate processor.)6 1938(Each processor keeps one sublist and passes the)7 2382 2 720 5556 t
( first sublist, {0, 1, 2, 9}, and sends the second, {16,)11 2516(In the example, processor 1 keeps the)6 1804 2 720 5836 t
( for)1 177( Similarly)1 517( 33}, to processor 3.)4 1000(17}, to processor 2 and the third, {24, 25, 27, 28, 30,)11 2626 4 720 6116 t
( each processor receives its portions of the data from the other)11 3064( Once)1 318(processors 2 and 3.)3 938 3 720 6396 t
(processors, it can merge the results into the final sorted array.)10 2959 1 720 6676 t
( sorting, it is not surprising that PSRS is)8 2045(Given the extensive literature on parallel)5 2025 2 970 6992 t
( example, Won and Sahni's balanced bin)6 2030( For)1 238( sort algorithms.)2 809(similar to other proposed)3 1243 4 720 7272 t
cleartomark
showpage
saveobj restore
%%EndPage: 8 8
%%Page: 9 9
/saveobj save def
mark
9 pagesetup
12 R f
(- 9 -)2 200 1 2780 500 t
(sort [26] and Abali, O)4 1081 1 720 860 t
(. .)1 54 1 1801 788 t
(zgu)1801 860 w
(. .)1 54 1 1974 788 t
( for Hypercube archi-)3 1056(ner and Bataineh's load balanced sort [1])6 2010 2 1974 860 t
( the algo-)2 478( differ from PSRS in the second phase of)8 2073( Both)1 307(tectures both resemble PSRS.)3 1462 4 720 1140 t
( elements in)2 610( balanced bin sort merges each processor's sample, keeping the)9 3159(rithm. The)1 551 3 720 1420 t
( the final partition phase,)4 1216( In)1 165(the odd positions and discarding those in the even positions.)9 2939 3 720 1700 t
(the sort has an upper bound of)6 1502 1 720 2028 t
12 I f
(p)2326 2112 w
12 R f
(3)2291 1956 w
12 I f
(n)2361 1956 w
12 S1 f
(_ __)1 166 1 2273 1992 t
12 R f
(elements that must be merged by a single processor)8 2550 1 2490 2028 t
( shown to have a bound of)6 1368(\(PSRS is)1 450 2 720 2416 t
12 I f
(p)2650 2500 w
12 R f
(2)2615 2344 w
12 I f
(n)2685 2344 w
12 S1 f
(_ __)1 166 1 2597 2380 t
12 R f
( load balanced sort)3 955( The)1 263(in the next section\).)3 1000 3 2822 2416 t
( pivots until it eventually)4 1350(iterates in phase 2, repeatedly modifying its selection of)8 2970 2 720 2756 t
( almost)1 368( this paper, it is shown that PSRS achieves)8 2184( In)1 177(achieves perfect load balancing.)3 1591 4 720 3036 t
(perfect load balancing in practice without the overhead of finding a perfect partition.)12 4068 1 720 3316 t
12 B f
( Analysis)1 465(3. Complexity)1 744 2 720 3736 t
12 R f
(In phases one and two of PSRS, all processors have roughly the same amount of)14 4070 1 970 4052 t
( divided because this)3 1011( phase three, it is not obvious how evenly the work is)11 2590( In)1 163(work to do.)2 556 4 720 4332 t
( can be shown that there)5 1193( it)1 103( However,)1 533(depends on how well the data has been partitioned.)8 2491 4 720 4612 t
(is an upper bound on the amount of work a processor must do.)12 2999 1 720 4892 t
12 B f
(Theorem 1)1 556 1 720 5208 t
12 R f
( phase 3 of PSRS, each processor merges less than 2)10 2518(: In)1 264 2 1276 5208 t
12 I f
(w)4068 5208 w
12 R f
(elements.)4178 5208 w
12 B f
(Proof)720 5524 w
12 R f
( any processor)2 693(: Consider)1 868 2 1006 5524 t
12 I f
(i)2597 5524 w
12 R f
(, where 1)2 442 1 2631 5524 t
12 S f
(\243)3123 5524 w
12 I f
(i)3239 5524 w
12 S f
(\243)3323 5524 w
12 I f
(p)3439 5524 w
12 R f
( are three cases:)3 763(. There)1 369 2 3499 5524 t
(1\))720 5840 w
12 I f
(i)861 5840 w
12 S f
(=)955 5840 w
12 R f
( 1 must be)3 534( the data to be merged by processor)7 1781(1. All)1 524 3 1081 5840 t
12 S f
(\243)3962 5840 w
12 I f
(y)4078 5840 w
9 R f
(1)4146 5864 w
12 R f
( there are)2 470(. Since)1 369 2 4201 5840 t
12 I f
(p)1440 6168 w
9 R f
(2)1515 6120 w
12 S f
(-)1630 6168 w
12 I f
(p)1756 6168 w
12 S f
(-)1876 6168 w
12 R f
(2)2032 6252 w
12 I f
(p)2032 6096 w
12 S1 f
(_ _)1 96 1 2014 6132 t
12 R f
(elements of the regular sample which are)6 1999 1 2156 6168 t
12 S f
(>)4189 6168 w
12 I f
(y)4315 6168 w
9 R f
(1)4383 6192 w
12 R f
(, there are at)3 602 1 4438 6168 t
(least \()1 298 1 1440 6556 t
12 I f
(p)1748 6556 w
9 R f
(2)1823 6508 w
12 S f
(-)1938 6556 w
12 I f
(p)2064 6556 w
12 S f
(-)2184 6556 w
12 R f
(2)2340 6640 w
12 I f
(p)2340 6484 w
12 S1 f
(_ _)1 96 1 2322 6520 t
12 R f
(\))2440 6556 w
12 I f
(p)2580 6640 w
(w)2570 6484 w
12 S1 f
(_ _)1 116 1 2552 6520 t
12 R f
(elements of)1 566 1 2717 6556 t
12 I f
(X)3321 6556 w
12 R f
(which are)1 477 1 3432 6556 t
12 S f
(>)3947 6556 w
12 I f
(y)4073 6556 w
9 R f
(1)4141 6580 w
12 R f
( other words,)2 646(. In)1 198 2 4196 6556 t
(there are at most)3 804 1 1440 6944 t
12 I f
(n)2276 6944 w
12 S f
(-)2396 6944 w
12 R f
(\()2522 6944 w
12 I f
(p)2572 6944 w
9 R f
(2)2647 6896 w
12 S f
(-)2762 6944 w
12 I f
(p)2888 6944 w
12 S f
(-)3008 6944 w
12 R f
(2)3164 7028 w
12 I f
(p)3164 6872 w
12 S1 f
(_ _)1 96 1 3146 6908 t
12 R f
(\))3264 6944 w
12 I f
(p)3404 7028 w
(w)3394 6872 w
12 S1 f
(_ _)1 116 1 3376 6908 t
12 R f
(= \()1 139 1 3536 6944 t
12 I f
(p)3685 6944 w
12 S f
(+)3805 6944 w
12 R f
(2)3961 7028 w
12 I f
(p)3961 6872 w
12 S1 f
(_ _)1 96 1 3943 6908 t
12 R f
(\))4061 6944 w
12 I f
(p)4201 7028 w
(w)4191 6872 w
12 S1 f
(_ _)1 116 1 4173 6908 t
12 S f
(<)4333 6944 w
12 R f
(2)4431 6944 w
12 I f
(w)4501 6944 w
12 R f
(elements)4612 6944 w
(of)1440 7284 w
12 I f
(X)1570 7284 w
12 R f
(which are)1 469 1 1673 7284 t
12 S f
(\243)2172 7284 w
12 I f
(y)2288 7284 w
9 R f
(1)2356 7308 w
12 R f
(.)2411 7284 w
cleartomark
showpage
saveobj restore
%%EndPage: 9 9
%%Page: 10 10
/saveobj save def
mark
10 pagesetup
12 R f
(- 10 -)2 260 1 2750 500 t
(2\))720 860 w
12 I f
(i)870 860 w
12 S f
(=)964 860 w
12 I f
(p)1090 860 w
12 R f
( by processor)2 682( the data to be merged)5 1164(. All)1 464 3 1150 860 t
12 I f
(p)3511 860 w
12 R f
(must be)1 399 1 3622 860 t
12 S f
(>)4072 860 w
12 I f
(y)4198 860 w
9 I f
(p)4266 884 w
9 S f
(-)4333 884 w
9 R f
(1)4398 884 w
12 R f
( are)1 197(. There)1 390 2 4453 860 t
(\()1440 1188 w
12 I f
(p)1490 1188 w
12 S f
(-)1610 1188 w
12 R f
(2 \))1 110 1 1736 1188 t
12 I f
(p)1866 1188 w
12 S f
(+)1986 1188 w
12 R f
(2)2142 1272 w
12 I f
(p)2142 1116 w
12 S1 f
(_ _)1 96 1 2124 1152 t
12 R f
( the regular sample which are)5 1467(elements of)1 569 2 2273 1188 t
12 S f
(\243)4349 1188 w
12 I f
(y)4465 1188 w
9 I f
(p)4533 1212 w
9 S f
(-)4600 1212 w
9 R f
(1)4665 1212 w
12 R f
(. That)1 320 1 4720 1188 t
(is, there are at least \()5 1195 1 1440 1576 t
12 I f
(p)2645 1576 w
9 R f
(2)2720 1528 w
12 S f
(-)2835 1576 w
12 R f
(2)2961 1576 w
12 I f
(p)3031 1576 w
12 S f
(+)3151 1576 w
12 R f
(2)3307 1660 w
12 I f
(p)3307 1504 w
12 S1 f
(_ _)1 96 1 3289 1540 t
12 R f
(\))3407 1576 w
12 I f
(p)3547 1660 w
(w)3537 1504 w
12 S1 f
(_ _)1 116 1 3519 1540 t
12 R f
(elements of)1 598 1 3717 1576 t
12 I f
(X)4386 1576 w
12 R f
(which are)1 510 1 4530 1576 t
12 S f
(\243)1440 1964 w
12 I f
(y)1556 1964 w
9 I f
(p)1624 1988 w
9 S f
(-)1691 1988 w
9 R f
(1)1756 1988 w
12 R f
(, or there are at most)5 1013 1 1811 1964 t
12 I f
(n)2859 1964 w
12 S f
(-)2979 1964 w
12 R f
(\()3105 1964 w
12 I f
(p)3155 1964 w
9 R f
(2)3230 1916 w
12 S f
(-)3345 1964 w
12 R f
(2)3471 1964 w
12 I f
(p)3541 1964 w
12 S f
(+)3661 1964 w
12 R f
(2)3817 2048 w
12 I f
(p)3817 1892 w
12 S1 f
(_ _)1 96 1 3799 1928 t
12 R f
(\))3917 1964 w
12 I f
(p)4057 2048 w
(w)4047 1892 w
12 S1 f
(_ _)1 116 1 4029 1928 t
12 S f
(<)4192 1964 w
12 R f
(2)4293 1964 w
12 I f
(w)4363 1964 w
12 R f
(elements of)1 562 1 4478 1964 t
12 I f
(X)1440 2304 w
12 R f
(which are)1 469 1 1543 2304 t
12 S f
(>)2042 2304 w
12 I f
(y)2168 2304 w
9 I f
(p)2236 2328 w
9 S f
(-)2303 2328 w
9 R f
(1)2368 2328 w
12 R f
(.)2423 2304 w
(3\) 1)1 193 1 720 2620 t
12 S f
(<)973 2620 w
12 I f
(i)1099 2620 w
12 S f
(<)1193 2620 w
12 I f
(p)1319 2620 w
12 R f
(. All data to be merged by processor)7 1769 1 1379 2620 t
12 I f
(i)3182 2620 w
12 R f
(must be)1 382 1 3250 2620 t
12 S f
(>)3666 2620 w
12 I f
(y)3792 2620 w
9 I f
(i)3860 2644 w
9 S f
(-)3907 2644 w
9 R f
(1)3972 2644 w
12 R f
(and)4061 2620 w
12 S f
(\243)4268 2620 w
12 I f
(y)4384 2620 w
9 I f
(i)4452 2644 w
12 R f
( are)1 180(. There)1 373 2 4487 2620 t
(\()1440 2948 w
12 I f
(i)1490 2948 w
12 S f
(-)1584 2948 w
12 R f
(2 \))1 110 1 1710 2948 t
12 I f
(p)1840 2948 w
12 S f
(+)1960 2948 w
12 R f
(2)2116 3032 w
12 I f
(p)2116 2876 w
12 S1 f
(_ _)1 96 1 2098 2912 t
12 R f
( regular sample which are)4 1268(elements of the)2 751 2 2244 2948 t
12 S f
(\243)4300 2948 w
12 I f
(y)4416 2948 w
9 I f
(i)4484 2972 w
9 S f
(-)4531 2972 w
9 R f
(1)4596 2972 w
12 R f
(, imply-)1 389 1 4651 2948 t
(ing)1440 3336 w
12 I f
(lb)1642 3336 w
12 S f
(=)1796 3336 w
12 R f
(\( \()1 90 1 1922 3336 t
12 I f
(i)2022 3336 w
12 S f
(-)2116 3336 w
12 R f
(2 \))1 110 1 2242 3336 t
12 I f
(p)2372 3336 w
12 S f
(+)2492 3336 w
12 R f
(2)2648 3420 w
12 I f
(p)2648 3264 w
12 S1 f
(_ _)1 96 1 2630 3300 t
12 R f
(\))2748 3336 w
12 I f
(p)2848 3420 w
(w)2838 3264 w
12 S1 f
(_ _)1 116 1 2820 3300 t
12 R f
(elements of)1 576 1 2996 3336 t
12 I f
(X)3620 3336 w
12 R f
( the other hand, there)4 1093(. On)1 254 2 3693 3336 t
(are \()1 234 1 1440 3724 t
12 I f
(p)1684 3724 w
12 S f
(-)1804 3724 w
12 I f
(i)1930 3724 w
12 R f
(\))1974 3724 w
12 I f
(p)2034 3724 w
12 S f
(-)2154 3724 w
12 R f
(2)2310 3808 w
12 I f
(p)2310 3652 w
12 S1 f
(_ _)1 96 1 2292 3688 t
12 R f
(elements of the regular sample which are)6 2077 1 2447 3724 t
12 S f
(>)4571 3724 w
12 I f
(y)4697 3724 w
9 I f
(i)4765 3748 w
12 R f
(. As)1 240 1 4800 3724 t
(well, there are)2 697 1 1440 4112 t
12 I f
(p)2214 4196 w
(w)2204 4040 w
12 S1 f
(_ _)1 116 1 2186 4076 t
12 S f
(-)2374 4112 w
12 R f
(1 elements that fall between)4 1377 1 2500 4112 t
12 I f
(y)3914 4112 w
9 I f
(i)3982 4136 w
12 R f
(and the next highest)3 986 1 4054 4112 t
( at least)2 596( there are)2 676( Thus)1 415(element in the regular sample.)4 1913 4 1440 4452 t
12 I f
(ub)1440 4780 w
12 S f
(=)1620 4780 w
12 R f
(\( \()1 90 1 1746 4780 t
12 I f
(p)1846 4780 w
12 S f
(-)1966 4780 w
12 I f
(i)2092 4780 w
12 R f
(\))2136 4780 w
12 I f
(p)2196 4780 w
12 S f
(-)2316 4780 w
12 R f
(2)2472 4864 w
12 I f
(p)2472 4708 w
12 S1 f
(_ _)1 96 1 2454 4744 t
12 S f
(+)2622 4780 w
12 R f
(1 \))1 110 1 2748 4780 t
12 I f
(p)2958 4864 w
(w)2948 4708 w
12 S1 f
(_ _)1 116 1 2930 4744 t
12 S f
(-)3118 4780 w
12 R f
( of)1 173(1 elements)1 560 2 3244 4780 t
12 I f
(X)4050 4780 w
12 R f
(which are)1 512 1 4196 4780 t
12 S f
(>)4781 4780 w
12 I f
(y)4907 4780 w
9 I f
(i)4975 4804 w
12 R f
(.)5010 4780 w
(Since the size of)3 797 1 1440 5168 t
12 I f
(X)2269 5168 w
12 R f
(is)2374 5168 w
12 I f
(n)2487 5168 w
12 R f
(, there are at most)4 866 1 2547 5168 t
12 I f
(n)3445 5168 w
12 S f
(-)3565 5168 w
12 I f
(ub)3691 5168 w
12 S f
(-)3871 5168 w
12 I f
(lb)3997 5168 w
12 R f
(= 2)1 158 1 4123 5168 t
12 I f
(w)4291 5168 w
12 S f
(-)4431 5168 w
12 I f
(p)4597 5252 w
(w)4587 5096 w
12 S1 f
(_ _)1 116 1 4569 5132 t
12 S f
(+)4757 5168 w
12 R f
(1)4883 5168 w
12 S f
(<)4974 5168 w
12 R f
(2)1440 5508 w
12 I f
(w)1510 5508 w
12 R f
(elements of)1 558 1 1620 5508 t
12 I f
(X)2208 5508 w
12 R f
(for processor)1 630 1 2311 5508 t
12 I f
(i)2971 5508 w
12 R f
(to merge.)1 454 1 3035 5508 t
(In conclusion, no processor merges more than 2)7 2386 1 720 5872 t
12 I f
(w)3116 5872 w
12 S f
(=)3256 5872 w
12 I f
(p)3447 5956 w
12 R f
(2)3412 5800 w
12 I f
(n)3482 5800 w
12 S1 f
(_ __)1 166 1 3394 5836 t
12 R f
(elements in the last phase of)5 1425 1 3615 5872 t
(PSRS. If)1 460 1 720 6212 t
12 I f
(p)1219 6212 w
9 R f
(2)1294 6164 w
12 R f
(doesn't divide)1 694 1 1388 6212 t
12 I f
(n)2121 6212 w
12 R f
( no processor merges more)4 1326(evenly, it is easy to prove that)6 1494 2 2220 6212 t
(than 2)1 297 1 720 6540 t
12 S f
(\351)1027 6540 w
12 I f
(p)1127 6624 w
(n)1127 6468 w
12 S1 f
(_ _)1 96 1 1109 6504 t
12 S f
(\371)1227 6540 w
12 R f
(elements.)1303 6540 w
( ini-)1 201( The)1 249( analysis for phase one is easy.)6 1496( The)1 249( time complexity of PSRS?)4 1323(What is the)2 552 6 970 6916 t
(tial Quicksort phase has time complexity)5 1979 1 720 7196 t
12 S f
(O)2731 7196 w
12 R f
(\()2817 7196 w
12 I f
(w)2857 7196 w
12 R f
(log)2987 7196 w
12 I f
(w)3191 7196 w
12 R f
( average case \262, representing)4 1394(\), in the)2 375 2 3271 7196 t
10 S1 f
(_ ______________)1 720 1 720 7316 t
10 R f
(\262 Quicksort is an O\()4 818 1 720 7436 t
10 I f
(w)1538 7436 w
10 R f
(log)1646 7436 w
10 I f
(w)1815 7436 w
10 R f
( but has a worst case that is O\()8 1244(\) algorithm in practice,)3 921 2 1882 7436 t
10 I f
(w)4047 7436 w
7 R f
(2)4125 7396 w
10 R f
( can)1 166(\). PSRS)1 346 2 4168 7436 t
( algorithm that has a worst-case performance of O\()8 2113(be changed to use an)4 875 2 720 7556 t
10 I f
(w)3708 7556 w
10 R f
(log)3816 7556 w
10 I f
(w)3985 7556 w
10 R f
(\), such as Mer-)3 628 1 4052 7556 t
cleartomark
showpage
saveobj restore
%%EndPage: 10 10
%%Page: 11 11
/saveobj save def
mark
11 pagesetup
12 R f
(- 11 -)2 260 1 2750 500 t
( consumed by each processor to sort)6 1759(the time)1 394 2 720 860 t
12 I f
(w)2906 860 w
12 R f
( phase)1 306( In)1 163(data using sequential Quicksort.)3 1552 3 3019 860 t
(two, sorting the regular sample using Quicksort requires)7 2754 1 720 1140 t
12 S f
(O)3511 1140 w
12 R f
(\()3597 1140 w
12 I f
(p)3637 1140 w
9 R f
(2)3712 1092 w
12 R f
(log)3817 1140 w
12 I f
(p)4021 1140 w
9 R f
(2)4096 1092 w
12 R f
( each)1 255( Then)1 312(\) time.)1 322 3 4151 1140 t
(processor performs)1 932 1 720 1420 t
12 I f
(p)1690 1420 w
12 S f
(-)1810 1420 w
12 R f
( no greater than)3 777(1 binary searches on sorted lists of)6 1711 2 1936 1420 t
12 I f
(w)4463 1420 w
12 R f
(elements.)4582 1420 w
(Hence the time complexity of phase two is)7 2060 1 720 1700 t
12 S f
(O)2810 1700 w
12 R f
(\()2896 1700 w
12 I f
(p)2936 1700 w
9 R f
(2)3011 1652 w
12 R f
(log)3116 1700 w
12 I f
(p)3320 1700 w
9 R f
(2)3395 1652 w
12 S f
(+)3510 1700 w
12 I f
(p)3636 1700 w
12 R f
(log)3746 1700 w
12 I f
(w)3950 1700 w
12 R f
( phase three, the)3 780(\). In)1 230 2 4030 1700 t
( processor is always less than 2)6 1562(size of data to be merged by any)7 1620 2 720 1980 t
12 I f
(w)3912 1980 w
12 R f
( the last phase)3 708(. Thus)1 340 2 3992 1980 t
(can finish in no more than)5 1259 1 720 2260 t
12 S f
(O)2009 2260 w
12 R f
(\(2)2095 2260 w
12 I f
(w)2205 2260 w
12 R f
(log)2335 2260 w
12 I f
(p)2539 2260 w
12 R f
(\) time.)1 315 1 2599 2260 t
( three phases gives a time complexity for PSRS of)9 2559(Summation of the times of all)5 1511 2 970 2576 t
(O\()720 2856 w
12 I f
(w)846 2856 w
12 R f
(log)976 2856 w
12 I f
(w)1180 2856 w
12 S f
(+)1320 2856 w
12 I f
(w)1446 2856 w
12 R f
(log)1576 2856 w
12 I f
(p)1780 2856 w
12 S f
(+)1900 2856 w
12 I f
(p)2026 2856 w
12 R f
(log)2136 2856 w
12 I f
(w)2340 2856 w
12 S f
(+)2480 2856 w
12 I f
(p)2606 2856 w
9 R f
(2)2681 2808 w
12 R f
(log)2786 2856 w
12 I f
(p)2990 2856 w
9 R f
(2)3065 2808 w
12 R f
( asymptotic to)2 701(\) which is)2 494 2 3120 2856 t
12 S f
(O)4354 2856 w
12 R f
(\()4440 2856 w
12 I f
(w)4480 2856 w
12 R f
(log)4610 2856 w
12 I f
(w)4814 2856 w
12 R f
(\) =)1 146 1 4894 2856 t
12 S f
(O)720 3184 w
12 R f
(\()806 3184 w
12 I f
(p)876 3268 w
(n)876 3112 w
12 S1 f
(_ _)1 96 1 858 3148 t
12 R f
(log)1016 3184 w
12 I f
(n)1220 3184 w
12 R f
(\) when)1 329 1 1280 3184 t
12 I f
(n)1639 3184 w
12 S f
(\263)1749 3184 w
12 I f
(p)1865 3184 w
9 R f
(3)1940 3136 w
12 R f
(.)1995 3184 w
(The bound on the size of the data to be merged in PSRS is an important difference)16 4070 1 970 3560 t
( Theoreti-)1 522( partition-based sorts, such as Quickmerge and PSS, don't have.)9 3212(which other)1 586 3 720 3840 t
(cally, PSRS is optimal when)4 1418 1 720 4120 t
12 I f
(n)2179 4120 w
12 S f
(\263)2289 4120 w
12 I f
(p)2405 4120 w
9 R f
(3)2480 4072 w
12 R f
( of the original data.)4 1020(, regardless of the distribution)4 1485 2 2535 4120 t
( few synchronization points, another advantage of PSRS)7 2751(Aside from easy scheduling and)4 1569 2 720 4400 t
( all three phases, each task accesses only)7 1982( In)1 164( of reference.)2 643(lies in its good per-task locality)5 1531 4 720 4680 t
(a small portion \(always less than 2)6 1730 1 720 4960 t
12 I f
(w)2460 4960 w
12 R f
(\) of the data and the accesses are highly localized.)9 2500 1 2540 4960 t
( The)1 252( reducing the average memory latency.)5 1897(This minimizes the amount of paging, hence)6 2171 3 720 5240 t
( each proces-)2 648( If)1 148( suitable for distributed memory multiprocessors.)5 2415(algorithm is especially)2 1109 4 720 5520 t
( approximately)1 727(sor is initially allocated a portion of)6 1726 2 720 5800 t
12 I f
(w)3205 5800 w
12 R f
(elements, then no data transmission)4 1723 1 3317 5800 t
( the second phase, only)4 1149( In)1 168(is required during the first phase.)5 1630 3 720 6080 t
12 I f
(p)3705 6080 w
12 R f
(\()3775 6080 w
12 I f
(p)3825 6080 w
12 S f
(-)3945 6080 w
12 R f
( elements need to)3 859(1 \))1 110 2 4071 6080 t
(be collected and)2 800 1 720 6360 t
12 I f
(p)1560 6360 w
12 S f
(-)1680 6360 w
12 R f
( the)1 188( In)1 171( required to be broadcast to all the processors.)8 2294(1 pivots are)2 581 4 1806 6360 t
(last phase, each processor has to send)6 1948 1 720 6640 t
12 I f
(p)2722 6640 w
12 S f
(-)2842 6640 w
12 R f
(1 sublists to the other)4 1123 1 2968 6640 t
12 I f
(p)4144 6640 w
12 S f
(-)4264 6640 w
12 R f
(1 processors.)1 650 1 4390 6640 t
( them)1 292(After a processor receives its sublists, it stores them locally and then works on)13 4028 2 720 6920 t
10 S1 f
(_ ______________)1 720 1 720 7040 t
10 R f
(gesort.)720 7160 w
cleartomark
showpage
saveobj restore
%%EndPage: 11 11
%%Page: 12 12
/saveobj save def
mark
12 pagesetup
12 R f
(- 12 -)2 260 1 2750 500 t
( is)1 130( total number of messages required in this phase)8 2462( The)1 264(totally independent of others.)3 1464 4 720 860 t
(therefore)720 1140 w
12 I f
(p)1183 1140 w
12 R f
(\()1293 1140 w
12 I f
(p)1343 1140 w
12 S f
(-)1463 1140 w
12 R f
( and the total data traffic is no greater than)9 2040(1 \))1 110 2 1589 1140 t
12 I f
(n)3769 1140 w
12 R f
(.)3829 1140 w
( the algorithm and its analysis is based)7 1884( First,)1 316( addressed.)1 537(Two final points need to be)5 1333 4 970 1456 t
( there are duplicates, then)4 1251( If)1 145( no duplicate elements in the list to be sorted.)9 2225(on there being)2 699 4 720 1736 t
( a large number of keys, each hav-)7 1701( even if there are)4 830( However,)1 534(Theorem 1 does not hold.)4 1255 4 720 2016 t
( there are keys)3 714( If)1 146( will be no problem.)4 996(ing a small number of duplicates, in practice there)8 2464 4 720 2296 t
( duplicates, parallel performance will degrade)5 2342(for which there are a large number of)7 1978 2 720 2576 t
( \(for example, by adding a secondary)6 1825(unless the algorithm is enhanced to cover this case)8 2495 2 720 2856 t
(key\).)720 3136 w
( than)1 244(Secondly, it is possible to use more)6 1738 2 970 3452 t
12 I f
(p)2989 3452 w
12 R f
(\()3099 3452 w
12 I f
(p)3149 3452 w
12 S f
(-)3269 3452 w
12 R f
( elements in the regular sample)5 1535(1 \))1 110 2 3395 3452 t
( chosen, the tighter the bound in Theorem 1)8 2155( more elements)2 751( The)1 254(for choosing the pivots.)3 1160 4 720 3732 t
( sample implies more overhead in determining the pivots,)8 3083( larger)1 348( A)1 184(can be made.)2 705 4 720 4012 t
( If)1 142(although, this could also be done in parallel.)7 2142 2 720 4292 t
12 I f
(n)3036 4292 w
12 R f
( enough, the more effective load)5 1559(is large)1 353 2 3128 4292 t
(balancing may offset this cost.)4 1467 1 720 4572 t
12 B f
( Results)1 404(4. Experimental)1 851 2 720 4992 t
12 R f
( a 64-processor Myrias)3 1140(The first version of PSRS was implemented in C to run on)11 2930 2 970 5308 t
( is expressed on the SPS-2 system by a single)9 2251( Parallelism)1 610(SPS-2 [4].)1 508 3 720 5588 t
12 I f
(pardo)4126 5588 w
12 R f
(extension to)1 591 1 4449 5588 t
( The)1 246(the programming languages Fortran and C.)5 2069 2 720 5868 t
12 I f
(pardo)3066 5868 w
12 R f
(causes independent loop iterations)3 1656 1 3384 5868 t
( can be heterogeneous and)4 1293( tasks)1 279( Parallel)1 436(to be executed in parallel as independent tasks.)7 2312 4 720 6148 t
( principle, gets \(by demand paging\) a virtual copy of its parent's)11 3158( task, in)2 388(recursive. Each)1 774 3 720 6428 t
( its own portion of the program independent of other con-)10 2930(address space, and manages)3 1390 2 720 6708 t
( the new parent state is formed by)7 1695( the tasks of a loop all complete,)7 1620( When)1 355(current tasks.)1 650 4 720 6988 t
12 I f
(merging)720 7268 w
12 R f
( four)1 261( there are)2 510( Specifically,)1 697(the results computed by all the parallel tasks.)7 2390 4 1182 7268 t
cleartomark
showpage
saveobj restore
%%EndPage: 12 12
%%Page: 13 13
/saveobj save def
mark
13 pagesetup
12 R f
(- 13 -)2 260 1 2750 500 t
12 I f
(merging)720 860 w
12 R f
(rules:)1150 860 w
(1\) no update:If no child task assigns to a variable, then the parent variable is unchanged.)15 4242 1 720 1176 t
( child task assigns to a variable, the variable in the)10 2612(2\) one task updates:If exactly one)5 1708 2 720 1492 t
(parent task is changed to the assigned variable.)7 2256 1 970 1772 t
( than one child task assign to a vari-)8 1794(3\) several tasks update with the same value:If more)8 2526 2 720 2088 t
( task is)2 369(able, but the values assigned are identical, then the variable in the parent)12 3701 2 970 2368 t
(changed to the assigned value.)4 1464 1 970 2648 t
( pattern will cause the value of the parent task variable to)11 2835(4\) otherwise:Any other update)3 1485 2 720 2964 t
(be unpredictable.)1 827 1 970 3244 t
( it would at completion of a corresponding serial)8 2482(The parent task then resumes just as)6 1838 2 720 3560 t
12 I f
(do/for)720 3840 w
12 R f
( fundamental idea behind this new memory model is to)9 2811( The)1 264(loop in Fortran/C.)2 902 3 1063 3840 t
(relieve memory contention at the price of memory replication.)8 2996 1 720 4120 t
( control mechanism that automati-)4 1672( SPS-2 system provides a transparent)5 1807(The Myrias)1 591 3 970 4436 t
( use of hardware resources, and)5 1651(cally schedules parallel tasks on PEs, optimizes the)7 2669 2 720 4716 t
( The)1 261( however, has both advantages and disadvantages.)6 2496( This,)1 318(manages all data motion.)3 1245 4 720 4996 t
( not worry about the)4 1074(major advantage is that it simplifies programming; a user need)9 3246 2 720 5276 t
( the other hand, this also)5 1206( On)1 212(details of task allocation, data motion, and synchronization.)7 2902 3 720 5556 t
( their own control scheme to execute one's specific)8 2478(makes it impossible for a user to have)7 1842 2 720 5836 t
( always desirable since the system's optimizer cannot take advan-)9 3278( is not)2 319(program. This)1 723 3 720 6116 t
(tage of the properties specific to a program.)7 2096 1 720 6396 t
( using randomly-generated 32-bit integers with various distribu-)7 3224(PSRS was tested)2 846 2 970 6712 t
( made for duplicate elements, of which there were undoubtedly a)10 3288( tests were)2 543(tions. No)1 489 3 720 6992 t
( the total number of)4 1033( long as the number of duplicates is small in relation to)11 2865(few. As)1 422 3 720 7272 t
cleartomark
showpage
saveobj restore
%%EndPage: 13 13
%%Page: 14 14
/saveobj save def
mark
14 pagesetup
12 R f
(- 14 -)2 260 1 2750 500 t
( of the array to be)5 905( size)1 229( The)1 258(elements, this will not significantly affect the performance.)7 2928 4 720 860 t
( were done using 2, 4,)5 1071( Experiments)1 671( 0.1 million to 8 million elements.)6 1660(sorted ranged from)2 918 4 720 1140 t
( this)1 215( data point presented in)4 1166( Each)1 310(8, 16, 32, and 64 processors on a dedicated machine.)9 2629 4 720 1420 t
( 20 program executions, each on a different set of)9 2444(section was obtained as the average of)6 1876 2 720 1700 t
(test data.)1 428 1 720 1980 t
( The)1 266( of Quicksort was used as the optimal sequential sort.)9 2745(An improved version)2 1059 3 970 2296 t
( the median of the first,)5 1213( First,)1 331(improvements consisted of two common modifications.)5 2776 3 720 2576 t
( subarrays with)2 740( Second,)1 446(middle, and last elements of the subarray were used as the pivot.)11 3134 3 720 2856 t
(size less than ten integers were sorted using linear insertion sort.)10 3097 1 720 3136 t
( PE on the SPS-2 can only sort at most 0.2 million 32-bit integers)13 3163(Unfortunately, one)1 907 2 970 3452 t
( we need to know the)5 1052( compute the speedups,)3 1142( To)1 200(due to the limitations of main memory.)6 1926 4 720 3732 t
( the Myrias SPS-2 when)4 1196(sequential sorting time of the improved Quicksort on)7 2592 2 720 4012 t
12 I f
(n)4545 4012 w
12 R f
(is larger)1 398 1 4642 4012 t
( sequential comparison-based sorting is)4 1918( the bound of)3 655( Since)1 333(than 0.2 million.)2 809 4 720 4292 t
12 S f
(O)4470 4292 w
12 R f
(\()4556 4292 w
12 I f
(n)4596 4292 w
12 R f
(log)4706 4292 w
12 I f
(n)4910 4292 w
12 R f
(\),)4970 4292 w
( reasonable to assume the time of sorting)7 1996(it is)1 182 2 720 4572 t
12 I f
(n)2932 4572 w
12 R f
(integers using the improved Quicksort on)5 2014 1 3026 4572 t
(one PE of the Myrias SPS-2 as follows:)7 1907 1 720 4852 t
12 I f
(t)2320 5202 w
9 I f
(PE)2369 5226 w
12 R f
(\()2499 5202 w
12 I f
(n)2549 5202 w
12 R f
(\))2619 5202 w
12 S f
(=)2769 5202 w
12 I f
(C n)1 190 1 2935 5202 t
12 R f
(log)3175 5202 w
12 I f
(n)3379 5202 w
12 R f
(where)720 5552 w
12 I f
(C)1050 5552 w
12 R f
(is a constant independent of size)5 1599 1 1168 5552 t
12 I f
(n)2805 5552 w
12 R f
( 0.2)1 189( times for lists of more than)6 1380(. Sequential)1 606 3 2865 5552 t
(million elements were calculated using the following formula:)7 2998 1 720 5832 t
12 I f
(t)1578 6230 w
9 I f
(PE)1627 6254 w
12 R f
(\()1757 6230 w
12 I f
(n)1807 6230 w
12 R f
(\))1877 6230 w
12 S f
(=)2027 6230 w
12 R f
( , 000)2 230( log 100)2 434(100 , 000)2 410 3 2223 6314 t
12 I f
(n)2573 6158 w
12 R f
(log)2683 6158 w
12 I f
(n)2887 6158 w
12 S1 f
(_ __________________)1 1110 1 2205 6194 t
12 S f
(\264)3377 6230 w
12 I f
(t)3493 6230 w
9 I f
(PE)3542 6254 w
12 R f
(\( 100 , 000 \))4 510 1 3672 6230 t
(where 0.4 million)2 878 1 720 6500 t
12 S f
(\243)1641 6500 w
12 I f
(n)1750 6500 w
12 S f
(\243)1853 6500 w
12 R f
(8 million and)2 669 1 1962 6500 t
12 I f
(t)2674 6500 w
9 I f
(PE)2723 6524 w
12 R f
( = 6.63 seconds, the experimental)5 1677(\( 100 , 000 \))4 510 2 2853 6500 t
( Quicksort to sort 0.1 million integers on one PE of the)11 2717(time for the improved sequential)4 1603 2 720 6780 t
( that if one uses this formula to compute)8 1979(SPS-2. Note)1 629 2 720 7060 t
12 I f
(t)3363 7060 w
9 I f
(PE)3412 7084 w
12 R f
( the result is almost)4 958(\( 200 , 000 \),)4 540 2 3542 7060 t
cleartomark
showpage
saveobj restore
%%EndPage: 14 14
%%Page: 15 15
/saveobj save def
mark
15 pagesetup
12 R f
(- 15 -)2 260 1 2750 500 t
(a perfect match with the corresponding experimental time.)7 2811 1 720 860 t
( also took an experimental approach)5 1768(To obtain more confidence in the speedups, we)7 2302 2 970 1176 t
( version of Quicksort on the)5 1475(to estimate the sequential sorting time of the improved)8 2845 2 720 1456 t
( of)1 150( experiments were done on a MIPS R1000, with 32 MByte)10 3015( Timing)1 434(Myrias SPS-2.)1 721 4 720 1736 t
( sort 4 million 32-bit integers without any memory shortage.)9 2927(main memory, that is able to)5 1393 2 720 2016 t
(Without memory limitations, we would have the following approximate equation:)9 3943 1 720 2296 t
12 I f
(t)2146 2802 w
9 I f
(R)2195 2826 w
9 R f
(1000)2257 2826 w
12 R f
(\()2457 2802 w
12 I f
(n)2507 2802 w
9 R f
(1)2582 2826 w
12 R f
(\))2647 2802 w
12 I f
(t)2212 2622 w
9 I f
(PE)2261 2646 w
12 R f
(\()2391 2622 w
12 I f
(n)2441 2622 w
9 R f
(1)2516 2646 w
12 R f
(\))2581 2622 w
12 S1 f
(_ _________)1 577 1 2128 2682 t
12 S f
(=)2877 2718 w
12 I f
(t)3073 2802 w
9 I f
(R)3122 2826 w
9 R f
(1000)3184 2826 w
12 R f
(\()3384 2802 w
12 I f
(n)3434 2802 w
9 R f
(2)3509 2826 w
12 R f
(\))3574 2802 w
12 I f
(t)3139 2622 w
9 I f
(PE)3188 2646 w
12 R f
(\()3318 2622 w
12 I f
(n)3368 2622 w
9 R f
(2)3443 2646 w
12 R f
(\))3508 2622 w
12 S1 f
(_ _________)1 577 1 3055 2682 t
12 R f
(where)720 3012 w
12 I f
(n)1048 3012 w
9 R f
(1)1123 3036 w
12 R f
(and)1214 3012 w
12 I f
(n)1423 3012 w
9 R f
(2)1498 3036 w
12 R f
( of data to be sorted, and)6 1226(are the sizes)2 599 2 1589 3012 t
12 I f
(t)3451 3012 w
9 I f
(R)3500 3036 w
9 R f
(1000)3562 3036 w
12 R f
(\()3762 3012 w
12 I f
(n)3812 3012 w
12 R f
(\) represents the sequen-)3 1158 1 3882 3012 t
( this estimate)2 661( Using)1 359( MIPS machine.)2 802(tial sorting time of the improved Quicksort on the)8 2498 4 720 3292 t
( results presented)2 843( The)1 250( speedups.)1 504(tends to result in higher sequential times, improving our)8 2723 4 720 3572 t
( approximation for the sequential running time, preferring to)8 2998(in this section use the first)5 1322 2 720 3852 t
( calculation,)1 591( times that were obtained by)5 1369( Sequential)1 570(err on the side of being conservative.)6 1790 4 720 4132 t
(instead of measurement, are indicated by italics.)6 2318 1 720 4412 t
( achieved.)1 494(Table 1 shows the time to sort using PSRS and Fig. 2 plots the speedups)14 3576 2 970 4728 t
( task granularity increases, offsetting the overheads of the)8 2830(As the problem size increases,)4 1490 2 720 5008 t
( with 64 processors gave)4 1203( 8,000,000 items)2 808( Sorting)1 418(algorithm, resulting in better speedups.)4 1891 4 720 5288 t
(a 44.4-fold speedup \262.)3 1070 1 720 5568 t
( been implemented.)2 955(For comparison purposes, PMS, Quickmerge and PSS have also)8 3115 2 970 5884 t
( as they are significantly better than both)7 2080(For brevity, only the PSS results are shown,)7 2240 2 720 6164 t
( time to sort the elements using PSS and Fig. 3)10 2281( 2 shows the)3 603( Table)1 335(PMS and Quickmerge.)2 1101 4 720 6444 t
10 S1 f
(_ ______________)1 720 1 720 6704 t
10 R f
( original)1 341( The)1 210( than those reported here [22].)5 1227(\262 Note that the original PSRS speedup results are less)9 2182 4 720 6824 t
( the cost for initially distributing the data, and the time taken to merge all the sort-)16 3326(results included)1 634 2 720 6944 t
( parallel sorting results assume the data is initially distri-)9 2326( Most)1 263( back to one processor.)4 945(ed sublists)1 426 4 720 7064 t
(buted and that merging the sorted sublists in one processor is not necessary.)12 3027 1 720 7184 t
cleartomark
showpage
saveobj restore
%%EndPage: 15 15
%%Page: 16 16
/saveobj save def
mark
16 pagesetup
12 R f
(- 16 -)2 260 1 2750 500 t
( 16)1 161( implementation of PSS used an initial sample of)8 2435( Our)1 256(plots the speedups achieved.)3 1398 4 720 860 t
12 I f
(p)4980 860 w
12 R f
( speedup increases with the value of)6 1812( The)1 259( over the data.)3 719(elements randomly spread)2 1290 4 720 1140 t
12 I f
(p)4843 1140 w
12 R f
(in)4946 1140 w
(general, but quickly tapers off when)5 1784 1 720 1420 t
12 I f
(p)2544 1420 w
12 R f
( is mainly because when)4 1218( This)1 285( than 16.)2 439(is greater)1 454 4 2644 1420 t
( of processors used increases, so does the probability that some processor may)12 3774(the number)1 546 2 720 1700 t
( it is possible that)4 925( Theoretically)1 721( merge significantly more data than its share.)7 2305(have to)1 369 4 720 1980 t
(some processor may have to perform a Mergesort on nearly all the data.)12 3453 1 720 2260 t
( is the claim that the data is evenly partitioned, it is)11 2687(Since the strength of PSRS)4 1383 2 970 2576 t
( The)1 248( successful it was.)3 874(important to measure how)3 1268 3 720 2856 t
12 I f
(RDFA)3142 2856 w
12 R f
(measure is used to quantify this.)5 1561 1 3479 2856 t
12 I f
(RDFA)720 3136 w
12 R f
(is the)1 262 1 1059 3136 t
12 I f
(R)1355 3136 w
12 R f
(elative)1428 3136 w
12 I f
(D)1783 3136 w
12 R f
( partition)1 444(eviation of the size of the largest)6 1594 2 1869 3136 t
12 I f
(F)3942 3136 w
12 R f
(rom the)1 376 1 4015 3136 t
12 I f
(A)4426 3136 w
12 R f
(verage size)1 541 1 4499 3136 t
(of the)1 277 1 720 3416 t
12 I f
(p)1027 3416 w
12 R f
(partitions, which is defined as follows:)5 1865 1 1117 3416 t
12 I f
(RDFA)2521 3814 w
12 S f
(=)2926 3814 w
12 I f
(w)3125 3898 w
(m)3122 3742 w
12 S1 f
(_ __)1 122 1 3104 3778 t
12 R f
(where)720 4272 w
12 I f
(m)1043 4272 w
12 R f
(is the size of the largest of the)7 1447 1 1160 4272 t
12 I f
(p)2638 4272 w
12 R f
(partitions and)1 660 1 2729 4272 t
12 I f
(w)3420 4272 w
12 S f
(=)3560 4272 w
12 I f
(p)3716 4356 w
(n)3716 4200 w
12 S1 f
(_ _)1 96 1 3698 4236 t
12 R f
( average size of the)4 934(, the)1 208 2 3806 4272 t
12 I f
(p)4980 4272 w
12 R f
(partitions. Since)1 817 1 720 4612 t
12 I f
(m)1571 4612 w
12 S f
(\263)1707 4612 w
12 I f
(w)1823 4612 w
12 R f
(, it is always the case that)6 1244 1 1903 4612 t
12 I f
(RDFA)3180 4612 w
12 S f
(\263)3535 4612 w
12 R f
( smaller the)2 568(1. The)1 339 2 3651 4612 t
12 I f
(RDFA)4591 4612 w
12 R f
(is,)4929 4612 w
( An)1 212(the more balanced the partitioning is.)5 1821 2 720 4892 t
12 I f
(RDFA)2789 4892 w
12 R f
(of)3130 4892 w
12 I f
(r)3266 4892 w
12 R f
(indicates that largest portion was)4 1608 1 3349 4892 t
12 I f
(r)4993 4892 w
12 R f
(times larger than optimal.)3 1238 1 720 5172 t
(The)970 5488 w
12 I f
(RDFA)1191 5488 w
12 R f
( PSS,)1 267( For)1 233( PSS in Table 4.)4 802(measures for PSRS are shown in Table 3 and)8 2207 4 1531 5488 t
( does the)2 469(the data clearly shows that as the number of processors increases so)11 3495 2 720 5768 t
12 I f
(RDFA)4735 5768 w
12 R f
( in the amount of work)5 1188( for a large number of processors, the disparity)8 2382(metric. Hence,)1 750 3 720 6048 t
( PSRS, the results are)4 1131( For)1 251(between processors grows, reducing the speedup possible.)6 2938 3 720 6328 t
(remarkably consistent, in all cases being within a few percent of perfect partitioning.)12 4073 1 720 6608 t
( the performance of)3 1009(From the data obtained, a few observations can be made on)10 3061 2 970 6924 t
(PSRS:)720 7204 w
cleartomark
showpage
saveobj restore
%%EndPage: 16 16
%%Page: 17 17
/saveobj save def
mark
17 pagesetup
12 R f
(- 17 -)2 260 1 2750 500 t
( number of PEs increase, the speedups are good provided that the problem)12 3746( the)1 191(1\) As)1 383 3 720 860 t
( both)1 249( When)1 351(size is large enough to give each PE a sufficient amount of work to do.)14 3470 3 970 1140 t
(the problem size and number of PEs double, so does the speedup.)11 3146 1 970 1420 t
( used a conservative approach in computing the speedups, the)9 3151( we have)2 465(2\) Although)1 704 3 720 1736 t
( 32-)1 194( has a speedup of 44.4 when sorting 8 million)9 2235( PSRS)1 346(results are still quite good.)4 1295 4 970 2016 t
( the other estimate for sequential time, 49-fold)7 2415( Using)1 373( 64 PEs.)2 449(bit integers with)2 833 4 970 2296 t
( beyond 64 can)3 735( trends suggest that additional processors)5 1990( The)1 249(speedups are obtained.)2 1096 4 970 2576 t
(be effectively utilized to further reduce sorting times)7 2536 1 970 2856 t
( to 1.0, perfect load balanc-)5 1352( 3 shows that PSRS RDFAs are consistently close)8 2445(3\) Table)1 523 3 720 3172 t
( the)1 177( size of the largest of)5 1010(ing. The)1 431 3 970 3452 t
12 I f
(p)2618 3452 w
12 R f
(partitions is very close to the average, indicating)7 2332 1 2708 3452 t
( a good representation of the original)6 1878(that the regular sample does indeed provide)6 2192 2 970 3732 t
( even when)2 549(data. Surprisingly,)1 918 2 970 4012 t
12 I f
(p)2469 4012 w
12 R f
(is small, the regular sample is still able to help par-)10 2479 1 2561 4012 t
( the)1 190( Theoretically,)1 743(tition the data evenly.)3 1079 3 970 4292 t
12 I f
(RDFA)3025 4292 w
12 R f
(of PSRS is only guaranteed to be)6 1667 1 3373 4292 t
( within a few per-)4 853( in practice, our experiments show it to be)8 2028( However,)1 529(less than two.)2 660 4 970 4572 t
( million)1 391( that with the PSS results, where the sorting of 8)10 2422( Contrast)1 478(cent of optimal.)2 779 4 970 4852 t
(integers on 64 processors was a factor of 2.4 off of the optimal partition.)13 3482 1 970 5132 t
( Two)1 284( size of the data is not large enough.)8 1772( runs poorly on the SPS-2 when the)7 1733(4\) PSRS)1 531 4 720 5448 t
( imple-)1 350( The)1 251( SPS-2 architecture.)2 968( first comes from the)4 1027( The)1 252(factors contribute to this.)3 1222 6 970 5728 t
(mentation of PSRS required using three)5 1924 1 970 6008 t
12 I f
(pardo)2926 6008 w
12 R f
( overhead of a)3 688(statements. The)1 787 2 3245 6008 t
12 I f
(pardo)4753 6008 w
12 R f
( be large enough)3 817( good performance, the problem size must)6 2074( For)1 235(is not insignificant.)2 944 4 970 6288 t
( The)1 279( amount of computation.)3 1282(to provide each individual processor a sufficient)6 2509 3 970 6568 t
( sampling cost in PSRS is basi-)6 1548( The)1 253( itself.)1 309(second factor comes from the algorithm)5 1960 4 970 6848 t
( in proportion to the total)5 1273( cost,)1 266( This)1 286(cally fixed, regardless of the size of the data.)8 2245 4 970 7128 t
cleartomark
showpage
saveobj restore
%%EndPage: 17 17
%%Page: 18 18
/saveobj save def
mark
18 pagesetup
12 R f
(- 18 -)2 260 1 2750 500 t
(sorting time, increases as the problem size decreases, reducing the speedup.)10 3634 1 970 860 t
( number of)2 539( is guaranteed to work well on any data distribution, as long as the)13 3250(5\) PSRS)1 531 3 720 1176 t
( example, using the IMOX data set from image)8 2378( For)1 241(duplicates is relatively small.)3 1451 3 970 1456 t
( were almost identi-)3 977(processing [7], which form a normal distribution, speedups that)8 3093 2 970 1736 t
(cal to those reported here were achieved [15].)7 2192 1 970 2016 t
( on the SPS-2 show that system activities account for the)10 2863( executions of PSRS)3 1021(6\) The)1 436 3 720 2332 t
( of the system time is spent in memory replication and)10 2775( Most)1 324(performance losses.)1 971 3 970 2612 t
( is spent in task)4 815( rest)1 221( The)1 263(merging required by the Myrias SPS-2 memory model.)7 2771 4 970 2892 t
( data-intensive prob-)2 1029( sorting is a)3 613( Since)1 345(creation, scheduling, and synchronization.)3 2083 4 970 3172 t
(lem, it is not a "good" problem for the Myrias SPS-2 to solve.)12 2973 1 970 3452 t
( the speedup relationships of the four algorithms implemented are as fol-)11 3553(In general,)1 517 2 970 3768 t
(lows:)720 4048 w
12 I f
(PMS)1832 4398 w
12 S f
(\243)2155 4398 w
12 I f
(Quickmerge)2311 4398 w
12 S f
(\243)2986 4398 w
12 I f
(PSS)3142 4398 w
12 S f
(\243)3425 4398 w
12 I f
(PSRS .)1 346 1 3581 4398 t
12 R f
( can't confirm Francis and)4 1392( We)1 257( poor.)1 311(The speedups of PMS are found to be rather)8 2360 4 720 4608 t
( due to the)3 543( results may be)3 767( These)1 360(Mathieson's claim that PMS has linear speedup [10].)7 2650 4 720 4888 t
( should not understate the overhead of schedul-)7 2286( one)1 204( However,)1 529(Myrias SPS-2 architecture.)2 1301 4 720 5168 t
( speedups of)2 648( The)1 270( algorithm.)1 553(ing and synchronization during the second phase of the)8 2849 4 720 5448 t
( Random)1 478( than those for PMS, but not as good as for PSS.)11 2442(Quickmerge are much better)3 1400 3 720 5728 t
(sampling seems to be a reasonable approach to parallel sorting, depending on the data)13 4320 1 720 6008 t
(distribution.)720 6288 w
( 44.5-fold)1 475( A)1 147( TC2000 [16].)2 685(PSRS has been implemented on the shared memory BBN)8 2763 4 970 6604 t
( sorting was)2 621( The)1 266(speedup was achieved sorting 8,000,000 elements on 64 processors.)8 3433 3 720 6884 t
( memory, while the global memory was used to communi-)9 2857(done in each processor's local)4 1463 2 720 7164 t
cleartomark
showpage
saveobj restore
%%EndPage: 18 18
%%Page: 19 19
/saveobj save def
mark
19 pagesetup
12 R f
(- 19 -)2 260 1 2750 500 t
(cate data.)1 453 1 720 860 t
12 B f
( on Hypercubes)2 801(5. PSRS)1 443 2 720 1280 t
12 R f
( Hypercube is a)3 752( A)1 147(In this section, PSRS is extended to run on Hypercubes machines.)10 3171 3 970 1596 t
( imagined to lie at the vertices of a)8 1712(multiprocessor in which the \(processor\) nodes can be)7 2608 2 720 1876 t
( based on this topology require modest intercon-)7 2349( Multiprocessors)1 838(multidimensional cube.)1 1133 3 720 2156 t
( of the classical interconnections to be)6 1963(nections, yet seem rich enough to allow many)7 2357 2 720 2436 t
( its homogeneity and sym-)4 1337( architecture is appealing because of)5 1814( The)1 260(easily constructed.)1 909 4 720 2716 t
( has been devoted at achieving good results \(for)8 2447( effort)1 317( Considerable)1 714(metry properties.)1 842 4 720 2996 t
( 13, 14, 21, 23, 24, 26]\).)6 1100(example, [1,)1 597 2 720 3276 t
(Assume)970 3592 w
12 I f
(p)1395 3592 w
12 R f
( nodes on a Hypercube and that)6 1566(is the number of)3 809 2 1493 3592 t
12 I f
(p)3907 3592 w
12 R f
( The)1 255(is a power of 2.)4 779 2 4006 3592 t
( from 0 to)3 514(nodes are indexed by a linear sequence ranging)7 2360 2 720 3872 t
12 I f
(p)3636 3872 w
12 S f
(-)3756 3872 w
12 R f
(1, with the neighboring)3 1158 1 3882 3872 t
( the)1 193( Assume)1 463( binary representations.)2 1157(nodes differing in exactly one bit position in their)8 2507 4 720 4152 t
(data is evenly distributed to all)5 1527 1 720 4432 t
12 I f
(p)2286 4432 w
12 R f
(nodes. The)1 565 1 2385 4432 t
12 I f
(n)2989 4432 w
12 R f
( sorted if all ele-)4 821(elements are said to be)4 1131 2 3088 4432 t
( the range of)3 609(ments are sorted at each node, and there is no element at any node that fits in)16 3711 2 720 4712 t
(values of any other node.)4 1210 1 720 4992 t
( sorting is usually measured in terms of the computing)9 2627(The complexity of Hypercube)3 1443 2 970 5308 t
( algorithm, which is an adaptation of)6 1887( Johnsson's)1 579( Presently,)1 559(and communication costs.)2 1295 4 720 5588 t
( best theoretical worst case bounds for)6 1956(Batcher's bitonic sorting algorithm [3], has the)6 2364 2 720 5868 t
( has)1 212( algorithm)1 522( His)1 250(Hypercube sorting [13].)2 1196 4 720 6148 t
12 S f
(O)2952 6148 w
12 R f
(\()3038 6148 w
12 I f
(w)3078 6148 w
12 R f
(log)3208 6148 w
12 I f
(w)3412 6148 w
12 S f
(+)3552 6148 w
12 I f
(w)3678 6148 w
12 R f
(log)3808 6148 w
9 R f
(2)3969 6100 w
12 I f
(p)4074 6148 w
12 R f
(\) computing com-)2 906 1 4134 6148 t
(plexity and)1 538 1 720 6476 t
12 S f
(O)1288 6476 w
12 R f
(\()1374 6476 w
12 I f
(w)1414 6476 w
12 R f
(log)1544 6476 w
9 R f
(2)1705 6428 w
12 I f
(p)1810 6476 w
12 R f
(\) communication complexity, with)3 1665 1 1870 6476 t
12 I f
(w)3565 6476 w
12 S f
(=)3705 6476 w
12 I f
(p)3861 6560 w
(n)3861 6404 w
12 S1 f
(_ _)1 96 1 3843 6440 t
12 R f
(.)3951 6476 w
( algorithm requires 4 phases:)4 1390( The)1 246(PSRS appears easily adaptable to Hypercubes.)5 2234 3 970 6852 t
( node sorts in parallel its local list of size)9 2070(1\) Each)1 489 2 720 7168 t
12 I f
(w)3320 7168 w
12 R f
( Each)1 311(with sequential Quicksort.)2 1288 2 3441 7168 t
cleartomark
showpage
saveobj restore
%%EndPage: 19 19
%%Page: 20 20
/saveobj save def
mark
20 pagesetup
12 R f
(- 20 -)2 260 1 2750 500 t
(node selects)1 587 1 970 860 t
12 I f
(p)1590 860 w
12 S f
(-)1710 860 w
12 R f
(1 elements evenly spaced from its local sorted list and sends them)11 3204 1 1836 860 t
(to a designated node, say node 0.)6 1587 1 970 1140 t
( it receives all)3 672(2\) After)1 503 2 720 1456 t
12 I f
(p)1925 1456 w
12 R f
(\()2035 1456 w
12 I f
(p)2085 1456 w
12 S f
(-)2205 1456 w
12 R f
( elements, node 0 selects)4 1192(1 \))1 110 2 2331 1456 t
12 I f
(p)3663 1456 w
12 S f
(-)3783 1456 w
12 R f
( same)1 278(1 pivots using the)3 853 2 3909 1456 t
( pivots to all other)4 993( then broadcasts the chosen)4 1434( It)1 164(method described previously.)2 1479 4 970 1736 t
( pivots, a binary search is used to partition each)9 2320( each node receives the)4 1124(nodes. After)1 626 3 970 2016 t
(local list into)2 631 1 970 2296 t
12 I f
(p)1631 2296 w
12 R f
(sublists.)1721 2296 w
( node)1 274(3\) Each)1 489 2 720 2612 t
12 I f
(i)1524 2612 w
12 R f
(\(0)1599 2612 w
12 S f
(\243)1749 2612 w
12 I f
(i)1865 2612 w
12 S f
(\243)1949 2612 w
12 I f
(p)2105 2612 w
12 S f
(-)2225 2612 w
12 R f
( \()1 82(1\) sends its)2 564 2 2351 2612 t
12 I f
(j)3027 2612 w
12 S f
(+)3121 2612 w
12 R f
( sublist to node)3 769(1 \)-th)1 244 2 3247 2612 t
12 I f
(j)4302 2612 w
12 R f
(,)4336 2612 w
12 I f
(j)4408 2612 w
12 S f
(=)4502 2612 w
12 R f
( ...,)1 162( ,)1 40( 1)1 110(0 ,)1 100 4 4628 2612 t
12 I f
(p)970 2892 w
12 S f
(-)1090 2892 w
12 R f
(1 ,)1 100 1 1216 2892 t
12 I f
(j)1376 2892 w
12 S f
(\271)1460 2892 w
12 I f
(i)1576 2892 w
12 R f
(.)1610 2892 w
( after it receives its)4 960(4\) Finally,)1 622 2 720 3208 t
12 I f
(p)2343 3208 w
12 S f
(-)2463 3208 w
12 R f
( all the)2 352(1 sublists, each node performs a merge on)7 2099 2 2589 3208 t
( sort completes after all nodes finish)6 1757( The)1 248( unsent.)1 376(received sublists plus the local one)5 1689 4 970 3488 t
(merging.)970 3768 w
( transfers are per-)3 858( Data)1 291(Note that no global synchronization is necessary between phases.)8 3171 3 720 4084 t
( data which must travel)4 1190( Thus)1 317(formed by passing messages between nearest neighbors.)6 2813 3 720 4364 t
(from node)1 505 1 720 4644 t
12 I f
(A)1263 4644 w
12 R f
(to node)1 365 1 1374 4644 t
12 I f
(B)1777 4644 w
12 R f
(must cross a sequence of nodes starting at node)8 2340 1 1888 4644 t
12 I f
(A)4266 4644 w
12 R f
(and ending at)2 663 1 4377 4644 t
(node)720 4924 w
12 I f
(B)983 4924 w
12 R f
(.)1056 4924 w
(The lower bound of the total computing time required for sorting)10 3356 1 970 5240 t
12 I f
(n)4379 5240 w
12 R f
(numbers is)1 548 1 4492 5240 t
12 S f
(O)720 5568 w
12 R f
(\()806 5568 w
12 I f
(p)846 5568 w
9 R f
(2)921 5520 w
12 R f
(log)1026 5568 w
12 I f
(p)1230 5568 w
9 R f
(2)1305 5520 w
12 S f
(+)1420 5568 w
12 I f
(w)1546 5568 w
12 R f
(log)1676 5568 w
12 I f
(p)1880 5568 w
12 S f
(+)2000 5568 w
12 I f
(w)2126 5568 w
12 R f
(log)2256 5568 w
12 I f
(w)2460 5568 w
12 S f
(+)2600 5568 w
12 I f
(p)2726 5568 w
12 R f
(log)2836 5568 w
12 I f
(w)3040 5568 w
12 R f
( to)1 144(\), which is asymptotic)3 1126 2 3120 5568 t
12 S f
(O)4440 5568 w
12 R f
(\()4526 5568 w
12 I f
(p)4596 5652 w
(n)4596 5496 w
12 S1 f
(_ _)1 96 1 4578 5532 t
12 R f
(log)4736 5568 w
12 I f
(n)4940 5568 w
12 R f
(\))5000 5568 w
(when)720 5908 w
12 I f
(n)1009 5908 w
12 S f
(\263)1119 5908 w
12 I f
(p)1235 5908 w
9 R f
(3)1310 5860 w
12 R f
( computing time alone is not sufficient to distinguish a parallel sort for)12 3399(. The)1 276 2 1365 5908 t
( this algorithm, the model of)5 1462( study the communication complexity of)5 2044(Hypercubes. To)1 814 3 720 6188 t
(Saad and Schultz is used [20]:)5 1452 1 720 6468 t
( a vector of length)4 910(a\) Moving)1 631 2 720 6784 t
12 I f
(m)2300 6784 w
12 R f
(from one node to a neighbor takes the time)8 2143 1 2426 6784 t
12 S f
(b +)1 192 1 4609 6784 t
12 I f
(m)4861 6784 w
12 S f
(t)4957 6784 w
12 R f
(,)5010 6784 w
(where)970 7064 w
12 S f
(b)1312 7064 w
12 R f
(represents the communication startup time and)5 2349 1 1428 7064 t
12 S f
(t)3827 7064 w
12 R f
( elemental transfer)2 933(, the)1 227 2 3880 7064 t
cleartomark
showpage
saveobj restore
%%EndPage: 20 20
%%Page: 21 21
/saveobj save def
mark
21 pagesetup
12 R f
(- 21 -)2 260 1 2750 500 t
(time.)970 860 w
( the same time to move the same data from one node to any number of its)16 3709( takes)1 287(b\) It)1 324 3 720 1176 t
(log)970 1456 w
12 I f
(p)1174 1456 w
12 R f
(neighbors.)1264 1456 w
(Further details can be found in [20].)6 1732 1 720 1772 t
( 2)1 125( and estimates for the times of data transfers required in phases 1,)12 3209(The algorithms)1 736 3 970 2088 t
( convenience,)1 696( For)1 264( 4 has no communication\).)4 1427(and 3 are sketched in Fig. 4 \(phase)7 1933 4 720 2368 t
( concatenation.)1 727( for)1 200(exponents applied to the binary bits 0 and 1 stand)9 2381 3 720 2648 t
( has log)2 406(Phase 1 of the algorithm)4 1236 2 970 2964 t
12 I f
(p)2662 2964 w
12 R f
( the)1 193(steps. At)1 467 2 2768 2964 t
12 I f
(j)3474 2964 w
12 R f
(th step, the algorithm transfers)4 1532 1 3508 2964 t
(2)720 3244 w
9 I f
(j)795 3196 w
9 S f
(-)835 3196 w
9 R f
(1)900 3196 w
12 I f
(p)1005 3244 w
12 R f
( elements collected)2 960(selected elements between two nodes, since the number of)8 2965 2 1115 3244 t
( gathering)1 490( the total time required for)5 1292( Therefore)1 537(doubles at every step.)3 1056 4 720 3524 t
12 I f
(p)4131 3524 w
9 R f
(2)4206 3476 w
12 R f
(elements,)4297 3524 w
12 I f
(p)4791 3524 w
12 R f
(per)4887 3524 w
(node, is)1 374 1 720 3804 t
9 I f
(j)1729 4336 w
9 S f
(=)1769 4336 w
9 R f
(1)1834 4336 w
17 S f
(S)1754 4246 w
9 R f
(log)1705 4100 w
9 I f
(p)1857 4100 w
12 R f
(\()1912 4210 w
12 S f
(b +)1 192 1 1962 4210 t
12 R f
(2)2214 4210 w
9 I f
(j)2289 4162 w
9 S f
(-)2329 4162 w
9 R f
(1)2394 4162 w
12 I f
(p)2459 4210 w
12 S f
(t)2529 4210 w
12 R f
(\))2592 4210 w
12 S f
(= b)1 232 1 2742 4210 t
12 R f
(log)3024 4210 w
12 I f
(p)3228 4210 w
12 S f
(+)3348 4210 w
12 R f
(\()3474 4210 w
12 I f
(p)3524 4210 w
12 S f
(-)3644 4210 w
12 R f
(1 \))1 110 1 3770 4210 t
12 I f
(p)3900 4210 w
12 S f
(t)3970 4210 w
12 R f
(.)4023 4210 w
(Phase 2 of the algorithm consists of log)7 1979 1 970 4558 t
12 I f
(p)2999 4558 w
12 R f
(steps, all requiring the same amount of)6 1940 1 3100 4558 t
( for broadcasting)2 970( the total time)3 904(time. Hence)1 689 3 720 4838 t
12 I f
(p)3391 4838 w
12 S f
(-)3511 4838 w
12 R f
(1 pivots in phase 2 is)5 1403 1 3637 4838 t
(\()720 5118 w
12 S f
(b +)1 192 1 770 5118 t
12 R f
(\()1022 5118 w
12 I f
(p)1072 5118 w
12 S f
(-)1192 5118 w
12 R f
(1 \))1 110 1 1318 5118 t
12 S f
(t)1448 5118 w
12 R f
(\) log)1 254 1 1511 5118 t
12 I f
(p)1815 5118 w
12 R f
(.)1875 5118 w
( equivalent to transposing a)4 1331(The data transfer operations in phase 3 are)7 2044 2 970 5434 t
12 I f
(p)4377 5434 w
12 S f
(\264)4487 5434 w
12 I f
(p)4603 5434 w
12 R f
(matrix,)4695 5434 w
(if the \()2 387 1 720 5714 t
12 I f
(j)1137 5714 w
12 S f
(+)1191 5714 w
12 R f
( node)1 295( sublist at)2 529(1 \)th)1 204 3 1277 5714 t
12 I f
(i)2367 5714 w
12 R f
(is viewed as an entry \()5 1237 1 2463 5714 t
12 I f
(i)3700 5714 w
12 R f
(,)3744 5714 w
12 I f
(j)3834 5714 w
12 R f
(\) of the matrix, where)4 1172 1 3868 5714 t
(0)720 5994 w
12 S f
(\243)830 5994 w
12 I f
(i)946 5994 w
12 R f
(,)990 5994 w
12 I f
(j)1080 5994 w
12 S f
(\243)1164 5994 w
12 I f
(p)1280 5994 w
12 S f
(-)1400 5994 w
12 R f
( we denote by \()4 751( formulate the algorithm,)3 1210(1. To)1 285 3 1526 5994 t
12 I f
(i)3782 5994 w
12 R f
(\))3826 5994 w
9 I f
(k)3881 6018 w
12 R f
(the bit in position)3 857 1 3964 5994 t
12 I f
(k)4854 5994 w
12 R f
(of)4940 5994 w
(the log)1 370 1 720 6280 t
12 I f
(p)1140 6280 w
12 R f
(-bit binary representation of number)4 1899 1 1200 6280 t
12 I f
(i)3168 6280 w
12 R f
(, and)1 272 1 3202 6280 t
12 I f
(i)3542 6280 w
12 S1 f
(_)3535 6169 w
9 I f
(k)3591 6220 w
12 R f
(the number whose binary)3 1331 1 3709 6280 t
(representation differs only in the)4 1574 1 720 6560 t
12 I f
(k)2325 6560 w
12 R f
(th bit from that of)4 861 1 2378 6560 t
12 I f
(i)3270 6560 w
12 R f
(. Let)1 251 1 3304 6560 t
12 I f
(L)3586 6560 w
9 I f
(i)3668 6584 w
9 R f
(,)3700 6584 w
9 I f
(j)3768 6584 w
12 R f
(be the \()2 364 1 3835 6560 t
12 I f
(j)4229 6560 w
12 S f
(+)4283 6560 w
12 R f
( sublist at)2 467(1 \)th)1 204 2 4369 6560 t
(node)720 6840 w
12 I f
(i)1005 6840 w
12 R f
(and)1091 6840 w
12 S f
(\357)1315 6840 w
12 I f
(L)1375 6840 w
9 I f
(i)1457 6864 w
9 R f
(,)1489 6864 w
9 I f
(j)1527 6864 w
12 S f
(\357)1562 6840 w
12 R f
(be its length, where 0)4 1115 1 1633 6840 t
12 S f
(\243)2798 6840 w
12 I f
(i)2914 6840 w
12 R f
(,)2958 6840 w
12 I f
(j)3048 6840 w
12 S f
(\243)3132 6840 w
12 I f
(p)3248 6840 w
12 S f
(-)3368 6840 w
12 R f
(1. [)1 211 1 3494 6840 t
12 I f
(L)3705 6840 w
9 I f
(i)3787 6864 w
9 R f
(,)3819 6864 w
9 I f
(j)3887 6864 w
12 R f
(] stands for the)3 781 1 3922 6840 t
12 I f
(p)4754 6840 w
12 S f
(\264)4864 6840 w
12 I f
(p)4980 6840 w
12 R f
( we have the following relations:)5 1579( Then)1 306(matrix as explained before.)3 1308 3 720 7120 t
cleartomark
showpage
saveobj restore
%%EndPage: 21 21
%%Page: 22 22
/saveobj save def
mark
22 pagesetup
12 R f
(- 22 -)2 260 1 2750 500 t
(0)1982 860 w
12 S f
(\243 \357)1 165 1 2092 860 t
12 I f
(L)2258 860 w
9 I f
(i)2340 884 w
9 R f
(,)2372 884 w
9 I f
(j)2410 884 w
12 S f
(\357 \243)1 166 1 2445 860 t
12 I f
(w)2661 860 w
12 R f
(, 0)1 180 1 2751 860 t
12 S f
(\243)2981 860 w
12 I f
(i)3097 860 w
12 R f
(,)3141 860 w
12 I f
(j)3231 860 w
12 S f
(\243)3315 860 w
12 I f
(p)3431 860 w
12 S f
(-)3551 860 w
12 R f
( \(1\))1 1263(1 ,)1 100 2 3677 860 t
9 I f
(j)1809 1462 w
9 S f
(=)1849 1462 w
9 R f
(0)1914 1462 w
17 S f
(S)1834 1372 w
9 I f
(p)1769 1226 w
9 S f
(-)1859 1226 w
9 R f
(1)1954 1226 w
12 S f
(\357)1999 1336 w
12 I f
(L)2059 1336 w
9 I f
(i)2141 1360 w
9 R f
(,)2173 1360 w
9 I f
(j)2211 1360 w
12 S f
(\357 =)1 216 1 2246 1336 t
12 I f
(w)2562 1336 w
12 R f
(, 0)1 180 1 2652 1336 t
12 S f
(\243)2882 1336 w
12 I f
(i)2998 1336 w
12 S f
(\243)3082 1336 w
12 I f
(p)3198 1336 w
12 S f
(-)3318 1336 w
12 R f
( Rand)1 353(1 ,)1 100 2 3444 1336 t
12 I f
(P)3917 1336 w
12 R f
(\(2\))4900 1336 w
9 I f
(i)1993 2040 w
9 S f
(=)2040 2040 w
9 R f
(0)2105 2040 w
17 S f
(S)2022 1950 w
9 I f
(p)1957 1804 w
9 S f
(-)2047 1804 w
9 R f
(1)2142 1804 w
12 S f
(\357)2187 1914 w
12 I f
(L)2247 1914 w
9 I f
(i)2329 1938 w
9 R f
(,)2361 1938 w
9 I f
(j)2399 1938 w
12 S f
(\357 <)1 216 1 2434 1914 t
12 R f
(2)2750 1914 w
12 I f
(w)2820 1914 w
12 R f
(, 0)1 180 1 2910 1914 t
12 S f
(\243)3140 1914 w
12 I f
(j)3266 1914 w
12 S f
(\243)3350 1914 w
12 I f
(p)3466 1914 w
12 S f
(-)3586 1914 w
12 R f
(1. \(3\))1 1328 1 3712 1914 t
( proof of \(3\) is the same as in Section 3.)10 1920( The)1 246(Proving \(1\) and \(2\) is trivial.)5 1384 3 720 2366 t
( the algorithm is to exchange data across opposite edges along the)11 3278(The principle of)2 792 2 970 2682 t
(log)720 2962 w
12 I f
(p)924 2962 w
12 R f
( that are in)3 535( the matrices)2 633( exchanging)1 622( first step consists of)4 1027( The)1 255(dimensions in turn.)2 945 6 1023 2962 t
(the upper right and lower left positions of the large 2)10 2688 1 720 3242 t
12 S f
(\264)3454 3242 w
12 R f
(2 block matrix obtained from)4 1474 1 3566 3242 t
([)720 3522 w
12 I f
(L)760 3522 w
9 I f
(i)842 3546 w
9 R f
(,)874 3546 w
9 I f
(j)942 3546 w
12 R f
( can again be split into four)6 1370( of the four)3 567( Each)1 309(] by splitting it into four equal parts.)7 1817 4 977 3522 t
(parts in the same manner.)4 1232 1 720 3802 t
( manner similar to what was done)6 1634(The next step deals with each of the four parts in a)11 2436 2 970 4118 t
( the sublists exchanged is still)5 1516(with the original matrix, and the total number of)8 2459 2 720 4398 t
12 I f
(p)4741 4398 w
12 R f
(. To)1 239 1 4801 4398 t
(obtain the time bound of each step, the following lemmas are introduced:)11 3520 1 720 4678 t
12 B f
(Lemma 1)1 497 1 720 4994 t
12 R f
( step)1 239(: At)1 371 2 1217 4994 t
12 I f
(k)1872 4994 w
12 R f
(\(1)1970 4994 w
12 S f
(\243)2120 4994 w
12 I f
(k)2236 4994 w
12 S f
(\243)2339 4994 w
12 R f
(log)2455 4994 w
12 I f
(p)2659 4994 w
12 R f
(\), all the sublists sent by any node must come)9 2321 1 2719 4994 t
(from 2)1 334 1 1440 5274 t
9 I f
(k)1781 5226 w
9 S f
(-)1843 5226 w
9 R f
(1)1908 5226 w
12 R f
(different rows and 2)3 1000 1 2003 5274 t
9 R f
(log)3010 5226 w
9 I f
(p)3162 5226 w
9 S f
(-)3252 5226 w
9 I f
(k)3347 5226 w
12 R f
( original)1 414(different columns of the)3 1189 2 3437 5274 t
(matrix.)1440 5554 w
12 B f
(Proof)720 5870 w
12 R f
( any node come from one single)6 1625( the first step, all the sublists sent by)8 1855(: At)1 554 3 1006 5870 t
(row and)1 398 1 1440 6198 t
(2)1907 6282 w
12 I f
(p)1907 6126 w
12 S1 f
(_ _)1 96 1 1889 6162 t
12 R f
( each step, the)3 704( After)1 321(different columns of the original matrix.)5 1979 3 2036 6198 t
( of the sublists to be sent doubles, while the)9 2324(number of different rows)3 1276 2 1440 6538 t
(number of different columns of the sublists to be sent reduces by half.)12 3363 1 1440 6818 t
12 B f
(Lemma 2)1 500 1 720 7134 t
12 R f
( step)1 241(: At)1 374 2 1220 7134 t
12 I f
(k)1882 7134 w
12 R f
(\(1)1982 7134 w
12 S f
(\243)2132 7134 w
12 I f
(k)2248 7134 w
12 S f
(\243)2351 7134 w
12 R f
(log)2467 7134 w
12 I f
(p)2671 7134 w
12 R f
( by any)2 389(\), the total size of all the sublists sent)8 1920 2 2731 7134 t
cleartomark
showpage
saveobj restore
%%EndPage: 22 22
%%Page: 23 23
/saveobj save def
mark
23 pagesetup
12 R f
(- 23 -)2 260 1 2750 500 t
(node is no larger than)4 1041 1 1440 860 t
12 I f
(min)2102 1312 w
12 S f
(\354)2302 1207 w
(\355)2302 1327 w
(\356)2302 1447 w
12 R f
(2)2361 1333 w
9 I f
(k)2428 1285 w
9 S f
(-)2490 1285 w
9 R f
(1)2555 1285 w
12 I f
(w)2620 1333 w
12 R f
(, 2)1 180 1 2710 1333 t
9 R f
(log)2897 1285 w
9 I f
(p)3049 1285 w
9 S f
(-)3139 1285 w
9 I f
(k)3234 1285 w
9 S f
(+)3319 1285 w
9 R f
(1)3414 1285 w
12 I f
(w)3479 1333 w
12 S f
(\374)3559 1207 w
(\375)3559 1327 w
(\376)3559 1447 w
12 I f
(.)3628 1312 w
12 B f
(Proof)720 1684 w
12 R f
( from Lemma 1, Equation \(2\), and Equation \(3\).)8 2312(: Straightforward)1 1195 2 1006 1684 t
(Hence step)1 529 1 970 2000 t
12 I f
(k)1529 2000 w
12 R f
(costs less than or equal to)5 1233 1 1612 2000 t
(2 \()1 110 1 1819 2452 t
12 S f
(b +)1 192 1 1939 2452 t
12 R f
(\()2191 2452 w
12 I f
(min)2241 2452 w
12 S f
(\354)2441 2347 w
(\355)2441 2467 w
(\356)2441 2587 w
12 R f
(2)2500 2473 w
9 I f
(k)2567 2425 w
9 S f
(-)2629 2425 w
9 R f
(1)2694 2425 w
12 I f
(w)2759 2473 w
12 R f
(, 2)1 140 1 2849 2473 t
9 R f
(log)2996 2425 w
9 I f
(p)3148 2425 w
9 S f
(-)3238 2425 w
9 I f
(k)3333 2425 w
9 S f
(+)3418 2425 w
9 R f
(1)3513 2425 w
12 I f
(w)3578 2473 w
12 S f
(\374)3658 2347 w
(\375)3658 2467 w
(\376)3658 2587 w
12 R f
(\))3727 2452 w
12 S f
(t)3787 2452 w
12 R f
(\) ,)1 90 1 3850 2452 t
(and the upper bound on the total communication time of phase 3 is)12 3213 1 720 2788 t
9 I f
(k)892 3366 w
9 S f
(=)954 3366 w
9 R f
(1)1019 3366 w
17 S f
(S)928 3276 w
9 R f
(log)879 3130 w
9 I f
(p)1031 3130 w
12 R f
(2 \()1 110 1 1086 3240 t
12 S f
(b +)1 192 1 1206 3240 t
12 R f
(\()1458 3240 w
12 I f
(min)1508 3240 w
12 S f
(\354)1708 3135 w
(\355)1708 3255 w
(\356)1708 3375 w
12 R f
(2)1767 3261 w
9 I f
(k)1834 3213 w
9 S f
(-)1896 3213 w
9 R f
(1)1961 3213 w
12 I f
(w)2026 3261 w
12 R f
(, 2)1 140 1 2116 3261 t
9 R f
(log)2263 3213 w
9 I f
(p)2415 3213 w
9 S f
(-)2505 3213 w
9 I f
(k)2600 3213 w
9 S f
(+)2685 3213 w
9 R f
(1)2780 3213 w
12 I f
(w)2845 3261 w
12 S f
(\374)2925 3135 w
(\375)2925 3255 w
(\376)2925 3375 w
12 R f
(\))2994 3240 w
12 S f
(t)3054 3240 w
12 R f
(\))3117 3240 w
12 S f
(=)3267 3240 w
12 R f
(2)3433 3240 w
12 S f
(b)3503 3240 w
12 R f
(log)3619 3240 w
12 I f
(p)3823 3240 w
12 S f
(+)3943 3240 w
12 I f
(p)4358 3324 w
12 R f
(6 \()1 110 1 4099 3168 t
13 S f
(\326` `)1 152 1 4219 3168 t
12 I f
(p)4301 3168 w
12 S f
(-)4441 3168 w
12 R f
(1 \))1 110 1 4567 3168 t
12 S1 f
(_ __________)1 614 1 4081 3204 t
12 I f
(n)4727 3240 w
12 S f
(t)4797 3240 w
12 R f
(.)4850 3240 w
( phases yields an upper bound of the total communication cost)10 3059(Summation over the three)3 1261 2 720 3576 t
(of PSRS as follows:)3 966 1 720 3856 t
(4)1490 4283 w
12 S f
(b)1560 4283 w
12 R f
(log)1676 4283 w
12 I f
(p)1880 4283 w
12 S f
(+)2000 4283 w
12 R f
(\()2126 4283 w
12 I f
(p)2465 4367 w
12 R f
(6 \()1 110 1 2206 4211 t
13 S f
(\326` `)1 152 1 2326 4211 t
12 I f
(p)2408 4211 w
12 S f
(-)2548 4211 w
12 R f
(1 \))1 110 1 2674 4211 t
12 S1 f
(_ __________)1 614 1 2188 4247 t
12 I f
(n)2834 4283 w
12 S f
(+)2954 4283 w
12 R f
(\()3080 4283 w
12 I f
(p)3130 4283 w
12 S f
(-)3250 4283 w
12 R f
(1 \) \()2 160 1 3376 4283 t
12 I f
(p)3546 4283 w
12 S f
(+)3666 4283 w
12 R f
(log)3792 4283 w
12 I f
(p)3996 4283 w
12 R f
(\) \))1 90 1 4066 4283 t
12 S f
(t)4176 4283 w
12 R f
(,)4239 4283 w
( time, and the latter one stands for the total)9 2077(where the first item represents the total startup)7 2243 2 720 4553 t
( total startup time is determined only by)7 2001( The)1 257(transmission time.)1 896 3 720 4833 t
12 I f
(p)3915 4833 w
12 R f
( a relatively)2 588(and is of)2 436 2 4016 4833 t
( When)1 362(low order.)1 509 2 720 5161 t
12 I f
(n)1637 5161 w
12 S f
(>>)1757 5161 w
12 R f
(log)1949 5161 w
12 I f
(p)2153 5161 w
12 R f
( to)1 141(, the total communication cost is asymptotic)6 2221 2 2213 5161 t
12 S f
(O)4622 5161 w
12 R f
(\()4708 5161 w
13 S f
(\326` `)1 152 1 4778 5274 t
12 I f
(p)4860 5274 w
(n)4829 5089 w
12 S1 f
(_ ___)1 198 1 4760 5125 t
12 R f
(\).)4970 5161 w
(The average communication time can be expected to be)8 2706 1 720 5530 t
12 I f
(much)3460 5530 w
12 R f
( Note)1 296(less than this bound.)3 992 2 3752 5530 t
( its neigh-)2 496(that no assumption is made that allows a node to send \(receive\) data to \(from\))14 3824 2 720 5810 t
(bors simultaneously.)1 997 1 720 6090 t
(Summarizing, the extension of PSRS on a Hypercube computer has)9 3439 1 970 6406 t
12 S f
(O)4460 6406 w
12 R f
(\()4546 6406 w
12 I f
(w)4586 6406 w
12 R f
(log)4716 6406 w
12 I f
(w)4920 6406 w
12 R f
(\))5000 6406 w
(computing complexity and)2 1318 1 720 6734 t
12 S f
(O)2081 6734 w
12 R f
(\()2167 6734 w
13 S f
(\326` `)1 152 1 2237 6847 t
12 I f
(p)2319 6847 w
(n)2288 6662 w
12 S1 f
(_ ___)1 198 1 2219 6698 t
12 R f
(\) communication complexity, where)3 1782 1 2429 6734 t
12 I f
(n)4254 6734 w
12 S f
(>)4357 6734 w
12 R f
(=)4423 6734 w
12 I f
(p)4533 6734 w
9 R f
(3)4608 6686 w
12 R f
(. Com-)1 377 1 4663 6734 t
( well, the)2 488( As)1 215(pared with Johnsson's algorithm, it has a better computing complexity.)9 3617 3 720 7103 t
cleartomark
showpage
saveobj restore
%%EndPage: 23 23
%%Page: 24 24
/saveobj save def
mark
24 pagesetup
12 R f
(- 24 -)2 260 1 2750 500 t
(startup time of the PSRS is much less than Johnsson's.)9 2635 1 720 860 t
( for the Intel iPSC/2-386 and iPSC/860 Hypercubes)7 2627(PSRS has been implemented)3 1443 2 970 1176 t
( in a)2 259( the iPSC/2-386 using 32 processors, sorting 4,000,000 items resulted)9 3598([16]. On)1 463 3 720 1456 t
( communication between pro-)3 1462( better results here are due to fast)7 1641( The)1 253(27.49-fold speedup.)1 964 4 720 1736 t
( is similar to the iPSC/2-386 except for the use of a faster proces-)13 3195( iPSC/860)1 497(cessors. The)1 628 3 720 2016 t
( for comparably sized problems, one would expect the speedups to)10 3279( Hence,)1 403( node.)1 301(sor per)1 337 4 720 2296 t
( a)1 99( 64 processors, sorting 8,000,000 items gave)6 2242( Using)1 364(be less than for the iPSC/2-386.)5 1615 4 720 2576 t
( were obtained using the same version of)7 1986( that results reported here)4 1230( Note)1 295(38-fold speedup.)1 809 4 720 2856 t
( machines, except for the parallel programming)6 2370(PSRS as used on the Myrias and BBN)7 1950 2 720 3136 t
( particu-)1 411( In)1 167( attempt was made to take advantage of the architecture.)9 2756( No)1 212(constructs used.)1 774 5 720 3416 t
( advantage of the savings possible by using)7 2115(lar, the communications patterns did not take)6 2205 2 720 3696 t
( Hypercube sorts have reported)4 1535( parallel)1 399( Other)1 341(the architecture's nearest neighbour links.)4 2045 4 720 3976 t
( in part because they exploit the communi-)7 2075( 24]\))1 220( \(for example, [1,)3 846(better results than PSRS)3 1179 4 720 4256 t
( PSRS implementation can be similarly extended.)6 2390( Our)1 246(cation structure of the Hypercube.)4 1637 3 720 4536 t
12 B f
( on LANs)2 486(6. PSRS)1 443 2 720 4956 t
12 R f
( LANs \(Local Area Net-)4 1270(The last decade has witnessed the explosive growth of)8 2800 2 970 5272 t
( on such a network may be physically distributed over a number of)12 3354( files)1 251(works\). Large)1 715 3 720 5552 t
( file)1 201(stations. A)1 555 2 720 5832 t
12 I f
(X)1516 5832 w
12 R f
(of size)1 327 1 1629 5832 t
12 I f
(n)1996 5832 w
12 R f
(is assumed to be distributed over)5 1631 1 2096 5832 t
12 I f
(p)3767 5832 w
12 R f
( The)1 256(stations of a LAN.)3 917 2 3867 5832 t
( into a linear sequence with station)6 1712(stations are logically ordered)3 1417 2 720 6112 t
12 I f
(i)3886 6112 w
12 S f
(+)3950 6112 w
12 R f
(1 being immediately)2 1004 1 4036 6112 t
( of station)2 500(to the right)2 545 2 720 6392 t
12 I f
(i)1804 6392 w
12 R f
(, where 1)2 460 1 1838 6392 t
12 S f
(\243)2348 6392 w
12 I f
(i)2464 6392 w
12 S f
(\243)2548 6392 w
12 I f
(p)2664 6392 w
12 S f
(-)2784 6392 w
12 R f
( initially assume an equal number of)6 1805(1. We)1 325 2 2910 6392 t
12 I f
(w)720 6720 w
12 S f
(=)860 6720 w
12 I f
(p)1016 6804 w
(n)1016 6648 w
12 S1 f
(_ _)1 96 1 998 6684 t
12 R f
( distributed sorting problem is to relocate some of)8 2449( The)1 252( station.)1 388(elements at each)2 808 4 1143 6720 t
( that each subfile at each station is sorted and each element at station)13 3381(the elements so)2 752 2 720 7060 t
12 I f
(i)4889 7060 w
12 R f
(is)4959 7060 w
cleartomark
showpage
saveobj restore
%%EndPage: 24 24
%%Page: 25 25
/saveobj save def
mark
25 pagesetup
12 R f
(- 25 -)2 260 1 2750 500 t
(less than or equal to any element at station)8 2045 1 720 860 t
12 I f
(i)2795 860 w
12 S f
(+)2859 860 w
12 R f
(1.)2945 860 w
( we refer to an Ethernet-type LAN, where all stations are)10 2759(To simplify the discussion,)3 1311 2 970 1176 t
( able to send a message to)6 1278( station on the LAN is)5 1095( Each)1 305(interconnected by a common bus.)4 1642 4 720 1456 t
( the cost of a distributed sort is dominated by)9 2269( Since)1 338(any other station\(s\) across the bus.)5 1713 3 720 1736 t
( of the required)3 806(the communication cost, its complexity is usually measured in terms)9 3514 2 720 2016 t
(number of messages and the total data traffic.)7 2190 1 720 2296 t
( been proposed for solving the distributed sort-)7 2332(Several distributed algorithms have)3 1738 2 970 2612 t
( each)1 252( In)1 163( on parallel Quicksort [25].)4 1317( algorithm is based)3 925( Wegner's)1 530( 19, 25].)2 380(ing problem [5,)2 753 7 720 2892 t
( the algorithm)2 688( the average,)2 619( On)1 211(iteration, every partition is divided into two smaller ones.)8 2802 4 720 3172 t
(has message complexity)2 1223 1 720 3452 t
12 S f
(O)2000 3452 w
12 R f
(\()2086 3452 w
12 I f
(p)2126 3452 w
12 R f
(log)2236 3452 w
12 I f
(p)2440 3452 w
12 R f
(\) and data traffic complexity)4 1477 1 2500 3452 t
12 S f
(O)4033 3452 w
12 R f
(\()4119 3452 w
12 I f
(n)4159 3452 w
12 R f
(log)4269 3452 w
12 I f
(p)4473 3452 w
12 R f
(\). Rotem,)1 507 1 4533 3452 t
( finding)1 391(Santoro and Sidney's algorithm [19] starts with)6 2358 2 720 3732 t
12 I f
(p)3512 3732 w
12 S f
(-)3632 3732 w
12 R f
(1 even partition points by)4 1282 1 3758 3732 t
(using a distributed version of the)5 1606 1 720 4012 t
12 I f
(k)2361 4012 w
12 R f
( each data item)3 736( that,)1 246( After)1 318(th selection algorithm [11].)3 1326 4 2414 4012 t
( complexity)1 615( algorithm has message)3 1252( The)1 288(is sent directly to its destination station.)6 2165 4 720 4292 t
12 S f
(O)720 4572 w
12 R f
(\()806 4572 w
12 I f
(p)846 4572 w
9 R f
(2)921 4524 w
12 R f
(log)1026 4572 w
12 I f
(n)1230 4572 w
12 R f
(\) and data traffic complexity)4 1369 1 1290 4572 t
12 S f
(O)2689 4572 w
12 R f
(\()2775 4572 w
12 I f
(n)2815 4572 w
12 R f
(\).)2875 4572 w
( low orders of complexity compared with other)7 2315(While both algorithms have relative)4 1755 2 970 4888 t
( algorithm)1 525( Wegner's)1 553(distributed sorting algorithms, they still suffer from drawbacks.)7 3242 3 720 5168 t
( traffic, while Rotem et al.'s algorithm requires too many)9 2804(requires a large amount of data)5 1516 2 720 5448 t
(messages.)720 5728 w
( multiprocessor, the algorithm is)4 1651(Although PSRS was developed for sorting on a)7 2419 2 970 6044 t
( was analyzed in Section 3, the algorithm has)8 2213( As)1 198(readily amenable to distributed sorting.)4 1909 3 720 6324 t
12 S f
(O)720 6604 w
12 R f
(\()806 6604 w
12 I f
(n)846 6604 w
12 R f
(\) data traffic complexity and)4 1489 1 906 6604 t
12 S f
(O)2456 6604 w
12 R f
(\()2542 6604 w
12 I f
(p)2582 6604 w
9 R f
(2)2657 6556 w
12 R f
(\) message complexity, which is a substantial)6 2328 1 2712 6604 t
(improvement over the)2 1062 1 720 6884 t
12 S f
(O)1812 6884 w
12 R f
(\()1898 6884 w
12 I f
(p)1938 6884 w
9 R f
(2)2013 6836 w
12 R f
(log)2118 6884 w
12 I f
(n)2322 6884 w
12 R f
(\) worst case for Rotem et al.'s algorithm.)7 1974 1 2382 6884 t
( workstations connected via)3 1365(PSRS has been implemented on a network of Sun 3/80)9 2705 2 970 7200 t
cleartomark
showpage
saveobj restore
%%EndPage: 25 25
%%Page: 26 26
/saveobj save def
mark
26 pagesetup
12 R f
(- 26 -)2 260 1 2750 500 t
( [15].)1 263( 500,000 items, a 4-fold speedup with 8 processors has been achieved)11 3389(Ethernet. For)1 668 3 720 860 t
( that restricted the amount of data)6 1623(These poor results were the result of a system limitation)9 2697 2 720 1140 t
(that could be sent between processors at a time.)8 2286 1 720 1420 t
12 B f
(7. Conclusions)1 772 1 720 1840 t
12 R f
( and synchronization are two)4 1423(Long memory latency and the overhead of scheduling)7 2647 2 970 2156 t
( parallel algorithm on present multipro-)5 1913(critical factors that greatly affect the speedup of a)8 2407 2 720 2436 t
( Sorting by Regular Sampling is intended to minimize both.)9 2912( Parallel)1 431(cessor architectures.)1 977 3 720 2716 t
( is simple to schedule and synchronize.)6 2042(It has a high per-task reference locality, yet)7 2278 2 720 2996 t
( architectures make it clear that good speedups for parallel)9 2933(Experiments on a variety of)4 1387 2 720 3276 t
( results reported)2 777( The)1 247( architectures is indeed achievable.)4 1682(sorting on present multiprocessor)3 1614 4 720 3556 t
( generally believed a hard problem)5 1701(here are quite encouraging, considering that sorting is)7 2619 2 720 3836 t
( indicates that good sorting performance for a variety)8 2573( success of PSRS)3 840( The)1 249(to parallelize.)1 658 4 720 4116 t
(of supercomputers is obtainable.)3 1563 1 720 4396 t
12 B f
(Acknowledgments)720 4816 w
12 R f
( referees supplied us with)4 1252(Paul Lu, John Shillington, Xiaobo Li and two anonymous)8 2818 2 970 5132 t
( Corporation pro-)2 841( Myrias Research)2 842( The)1 247(constructive suggestions for improving the paper.)5 2390 4 720 5412 t
(vided us with machine time.)4 1360 1 720 5692 t
12 B f
(References)720 5972 w
12 R f
( O)1 130( B.,)1 170(1. Abali,)1 597 3 720 6184 t
(. .)1 54 1 1617 6112 t
(zgu)1617 6184 w
(. .)1 54 1 1790 6112 t
( on Hypercube Mul-)3 1021( Load Balanced Sort)3 1025( A.,)1 176( and Bataineh,)2 718(ner, F.)1 310 5 1790 6184 t
(tiprocessors,)1020 6324 w
12 I f
(5th Distributed Memory Computing Conference)4 2309 1 1655 6324 t
12 R f
(, 1990, 230-236.)2 790 1 3994 6324 t
( S.G.,)1 273(2. Akl,)1 510 2 720 6500 t
12 I f
(Parallel Sorting Algorithms)2 1345 1 1533 6500 t
12 R f
(, Academic Press, Orlando, Florida, 1985.)5 2021 1 2878 6500 t
( and Their Applications,)3 1198( Sorting Networks)2 899( K.E.,)1 279(3. Batcher,)1 703 4 720 6676 t
12 I f
(Proceedings of the 1968)3 1201 1 3839 6676 t
(Spring Joint Computer Conference 32)4 1835 1 1020 6816 t
12 R f
(, \(1968\), 307-314, AFIPS Press.)4 1541 1 2855 6816 t
( PAMS/SPS-2)1 697( D.,)1 176( and Wilson,)2 619( M.)1 167( Walker,)1 417( R.,)1 170( Manson,)1 451( K.,)1 176( Bobey,)1 377( M.,)1 197(4. Beltrametti,)1 873 11 720 6992 t
(System Overview,)1 887 1 1020 7132 t
12 I f
(Supercomputing Symposium)1 1363 1 1937 7132 t
12 R f
(, 1989, 63-71.)2 670 1 3300 7132 t
( for Sorting Files in a)5 1162( An Algorithm with Decentralized Control)5 2176( T.Y.,)1 279(5. Cheung,)1 703 4 720 7308 t
cleartomark
showpage
saveobj restore
%%EndPage: 26 26
%%Page: 27 27
/saveobj save def
mark
27 pagesetup
12 R f
(- 27 -)2 260 1 2750 500 t
(Network,)1020 860 w
12 I f
(Journal of Parallel and Distributed Computing 7)6 2366 1 1499 860 t
12 R f
(, \(1989\), 464-481.)2 870 1 3865 860 t
( with Multiprocessor Algorithms,)3 1681( Experience)1 591( J.,)1 137(6. Deminet,)1 744 4 720 1036 t
12 I f
(IEEE Transactions on)2 1114 1 3926 1036 t
(Computers C-31)1 797 1 1020 1176 t
12 R f
(, \(1982\), 278-288.)2 870 1 1817 1176 t
( Clustering Techniques: The User's Dilemma,)5 2266( A.K.,)1 292( and Jain,)2 475( R.C.)1 250(7. Dubes,)1 636 5 720 1352 t
12 I f
(Pattern)4679 1352 w
(Recognition 8)1 671 1 1020 1492 t
12 R f
(, \(1976\), 247-260.)2 870 1 1691 1492 t
( the Parallel Quick-)3 977( Analysis of the Performance of)5 1591( N.Y.,)1 292( and Yousif,)2 614( D.J.)1 223(8. Evans,)1 623 6 720 1668 t
(sort Method,)1 615 1 1020 1808 t
12 I f
(BIT 25)1 330 1 1665 1808 t
12 R f
(, \(1985\), 106-112.)2 870 1 1995 1808 t
( Neighbor Sort and Two-way Merge)5 1878( The Parallel)2 664( N.Y.,)1 292( and Yousif,)2 640( D.J.)1 223(9. Evans,)1 623 6 720 1984 t
(Algorithm,)1020 2124 w
12 I f
(Parallel Computing 3)2 1049 1 1582 2124 t
12 R f
(, \(1986\), 85-90.)2 750 1 2631 2124 t
( Parallel Sort for Shared Memory)5 1651( A Benchmark)2 715( I.D.,)1 246( and Mathieson,)2 787( R.S.)1 237(10. Francis,)1 684 6 720 2300 t
(Multiprocessors,)1020 2440 w
12 I f
(IEEE Transactions on Computers 37)4 1775 1 1856 2440 t
12 R f
(, 12 \(1988\), 1619-1626.)3 1140 1 3631 2440 t
( Selection in Distributed Networks,)4 1744( Tradeoffs for)2 686( G.N.,)1 292(11. Frederickson,)1 957 4 720 2616 t
12 I f
(Proceedings)4440 2616 w
(of the 2nd ACM Symposium on the Principles of Distributed Computing)10 3669 1 1020 2756 t
12 R f
(, 1983,)1 351 1 4689 2756 t
(154-160.)1020 2896 w
( Sampling,)1 536( Parallel Sorting and Data Partitioning by)6 2070( Y.C.,)1 286( and Chow,)2 575( J.S.)1 204(12. Huang,)1 649 6 720 3072 t
12 I f
(7th International Computer Software and Applications Conference)6 3220 1 1020 3212 t
12 R f
(, 1983, 627-631.)2 790 1 4240 3212 t
( Combining Parallel and Sequential Sorting on a Boolean n-cube,)9 3289( S.L.,)1 260(13. Johnsson,)1 771 3 720 3388 t
12 I f
(International Conference on Parallel Processing)4 2358 1 1020 3528 t
12 R f
(, 1984.)1 330 1 3378 3528 t
( Parallel Sorting on the Symult 2010,)6 1951( Y.W.,)1 319( and Tung,)2 570( P.P.)1 224(14. Li,)1 437 5 720 3704 t
12 I f
(5th Distributed)1 761 1 4279 3704 t
(Memory Computing Conference)2 1546 1 1020 3844 t
12 R f
(, 1990, 224-229.)2 790 1 2566 3844 t
( Parallel Sorting by Regular)4 1367( J.,)1 137( and Shillington,)2 812( H.)1 146( Shi,)1 227( J.,)1 137( Schaeffer,)1 525( P.,)1 157( Lu,)1 199( X.,)1 176(15. Li,)1 437 11 720 4020 t
( 91-6 Department of Computing Science, University of)7 2902(Sampling, Tech. Rep.)2 1118 2 1020 4160 t
(Alberta, 1991.)1 690 1 1020 4300 t
( report,)1 368( Sorting on MIMD Architectures, CMPUT 535)6 2385( J.,)1 137( and Shillington,)2 840( P.)1 127(16. Lu,)1 463 6 720 4476 t
(Department of Computing Science, University of Alberta, 1990.)7 3090 1 1020 4616 t
( A Paradigm for Multiproces-)4 1457( Problem-heap:)1 744( J.,)1 137( and Staunstrup,)2 790( P.)1 127(17. Moller-Nielsen,)1 1065 6 720 4792 t
(sor Algorithms,)1 756 1 1020 4932 t
12 I f
(Parallel Computers 4)2 1042 1 1806 4932 t
12 R f
(, \(1987\), 63-74.)2 750 1 2848 4932 t
( Coupled Multiprocessors,)2 1339( Parallel Sorting Algorithms for Tightly)5 2077( M.J.,)1 274(18. Quinn,)1 630 4 720 5108 t
12 I f
(Parallel Computing 6)2 1049 1 1020 5248 t
12 R f
(, \(1988\), 349-357, North-Holland.)3 1637 1 2069 5248 t
( Distributed Sorting,)2 1025( J.B.,)1 247( and Sidney,)2 635( N.)1 146( Santoro,)1 453( D.,)1 176(19. Rotem,)1 651 7 720 5424 t
12 I f
(IEEE Transactions)1 938 1 4102 5424 t
(on Computers 34)2 827 1 1020 5564 t
12 R f
(, 4 \(1985\), 372-275.)3 960 1 1847 5564 t
( Data Communication in Hypercubes,)4 1982( M.H.,)1 313( and Schultz,)2 706( Y.)1 146(20. Saad,)1 563 5 720 5740 t
12 I f
(Journal of)1 539 1 4501 5740 t
(Parallel and Distributed Computing 6)4 1838 1 1020 5880 t
12 R f
(, 1 \(1989\), 115-135.)3 960 1 2858 5880 t
( on Hypercubes, in)3 975( Sorting)1 407( L.R.,)1 273( and Ziegler,)2 654( S.)1 127(21. Seidel,)1 631 6 720 6056 t
12 I f
(Hypercube Multiproces-)1 1200 1 3840 6056 t
(sors)1020 6196 w
12 R f
(, M.T. Heath \(ed.\), SIAM, 1987, 285-291.)6 2019 1 1221 6196 t
( Computers, M.Sc. thesis, Department)4 1901( Parallel Sorting on Multiprocessor)4 1752( H.,)1 176(22. Shi,)1 491 4 720 6372 t
(of Computing Science, University of Alberta, 1990.)6 2493 1 1020 6512 t
( Parallel Sorting on the Hypercube Concurrent Processor,)7 2804( T.,)1 163(23. Tang,)1 576 3 720 6688 t
12 I f
(5th Distributed)1 740 1 4300 6688 t
(Memory Computing Conference)2 1546 1 1020 6828 t
12 R f
(, 1990, 237-240.)2 790 1 2566 6828 t
( Algorithm for Hypercubes, in)4 1518( Hyperquicksort: A Fast Sorting)4 1599( B.,)1 170(24. Wagar,)1 649 4 720 7004 t
12 I f
(Hyper-)4701 7004 w
(cube Multiprocessors)1 1039 1 1020 7144 t
12 R f
(, M.T. Heath \(ed.\), SIAM, 1987, 292-299.)6 2019 1 2059 7144 t
( Sorting a Distributed File in a Network,)7 2119( L.M.,)1 300(25. Wegner,)1 709 3 720 7320 t
12 I f
(Computer Networks 8)2 1106 1 3904 7320 t
12 R f
(,)5010 7320 w
cleartomark
showpage
saveobj restore
%%EndPage: 27 27
%%Page: 28 28
/saveobj save def
mark
28 pagesetup
12 R f
(- 28 -)2 260 1 2750 500 t
(\(1984\), 451-461.)1 810 1 1020 860 t
( Sort for Hypercube Multicomputers,)4 1806( A Balanced Bin)3 808( S.,)1 157( and Sahni,)2 545( Y.)1 146(26. Won,)1 563 6 720 1036 t
12 I f
(Jour-)4780 1036 w
(nal of Supercomputing 2)3 1185 1 1020 1176 t
12 R f
(, \(1988\), 435-448.)2 870 1 2205 1176 t
cleartomark
showpage
saveobj restore
%%EndPage: 28 28
%%Page: 29 29
/saveobj save def
mark
29 pagesetup
12 R f
(- 29 -)2 260 1 2750 500 t
12 B f
( PSRS Algorithm)2 887(Appendix. The)1 791 2 720 860 t
(procedure)720 1140 w
12 R f
(PSRS\()1276 1140 w
12 I f
(array)1597 1140 w
12 R f
(,)1874 1140 w
12 I f
(n)1934 1140 w
12 R f
(,)2004 1140 w
12 I f
(p)2064 1140 w
12 R f
(\))2124 1140 w
(#)720 1280 w
12 I f
(array)810 1280 w
12 R f
([ 0 :)2 154 1 1087 1280 t
12 I f
(n)1251 1280 w
12 S f
(-)1341 1280 w
12 R f
( array to be sorted,)4 897(1 ]:)1 144 2 1427 1280 t
12 I f
(n)2498 1280 w
12 R f
(: size of the array,)4 864 1 2558 1280 t
12 I f
(p)3452 1280 w
12 R f
(: number of processors)3 1098 1 3512 1280 t
12 B f
(begin)720 1420 w
12 R f
(# Divide the array into)4 1088 1 1080 1560 t
12 I f
(p)2198 1560 w
12 R f
(contiguous lists and sort each in parallel.)6 1962 1 2288 1560 t
(# Select)1 384 1 1080 1700 t
12 I f
(p)1494 1700 w
12 S f
(-)1614 1700 w
12 R f
(1 elements evenly spaced from each of the)7 2044 1 1740 1700 t
12 I f
(p)3814 1700 w
12 R f
(sorted lists)1 520 1 3904 1700 t
(# as the regular sample and store them in)8 1970 1 1080 1840 t
12 I f
(sample)3080 1840 w
12 R f
([ 0 :)2 154 1 3430 1840 t
12 I f
(p)3594 1840 w
12 R f
(\()3664 1840 w
12 I f
(p)3714 1840 w
12 S f
(-)3834 1840 w
12 R f
(1 \))1 110 1 3960 1840 t
12 S f
(-)4090 1840 w
12 R f
(1 ].)1 140 1 4176 1840 t
12 I f
(size)1080 1980 w
12 S f
(= \353)1 186 1 1321 1980 t
12 R f
(\()1517 1980 w
12 I f
(n)1567 1980 w
12 S f
(+)1657 1980 w
12 I f
(p)1743 1980 w
12 S f
(-)1833 1980 w
12 R f
(1 \))1 110 1 1919 1980 t
12 S f
(/)2049 1980 w
12 I f
(p)2093 1980 w
12 S f
(\373)2163 1980 w
12 I f
(rsize)1080 2120 w
12 S f
(= \353)1 186 1 1368 2120 t
12 R f
(\()1564 2120 w
12 I f
(size)1614 2120 w
12 S f
(+)1825 2120 w
12 I f
(p)1911 2120 w
12 S f
(-)2001 2120 w
12 R f
(1 \))1 110 1 2087 2120 t
12 S f
(/)2217 2120 w
12 I f
(p)2261 2120 w
12 S f
(\373)2331 2120 w
12 B f
(for)1080 2260 w
12 I f
(i)1263 2260 w
12 S f
(=)1357 2260 w
12 R f
(0)1483 2260 w
12 B f
(to)1573 2260 w
12 I f
(p)1703 2260 w
12 S f
(-)1793 2260 w
12 R f
(1)1879 2260 w
12 B f
(do in parallel)2 683 1 1969 2260 t
12 I f
(start)1440 2400 w
12 S f
(=)1722 2400 w
12 I f
(i)1848 2400 w
12 S f
(\264)1892 2400 w
12 I f
(size)1968 2400 w
(end)1440 2540 w
12 S f
(=)1673 2540 w
12 R f
(\()1799 2540 w
12 I f
(i)1849 2540 w
12 S f
(+)1913 2540 w
12 R f
(1 \))1 110 1 1999 2540 t
12 S f
(\264)2129 2540 w
12 I f
(size)2205 2540 w
12 S f
(-)2416 2540 w
12 R f
(1 #)1 150 1 2502 2540 t
12 S f
(=)2702 2540 w
12 I f
(start)2828 2540 w
12 S f
(+)3110 2540 w
12 I f
(size)3236 2540 w
12 S f
(-)3477 2540 w
12 R f
(1)3603 2540 w
12 B f
(if)1440 2680 w
12 I f
(end)1544 2680 w
12 S f
(\263)1767 2680 w
12 I f
(n)1883 2680 w
12 B f
(then)1973 2680 w
12 I f
(end)1800 2820 w
12 S f
(=)2033 2820 w
12 I f
(n)2159 2820 w
12 S f
(-)2249 2820 w
12 R f
(1)2335 2820 w
(# Sort subarray)2 734 1 1440 2960 t
12 I f
(array)2204 2960 w
12 R f
([)2481 2960 w
12 I f
(start)2531 2960 w
12 R f
(:)2763 2960 w
12 I f
(end)2807 2960 w
12 R f
(] with sequential Quicksort.)3 1336 1 2990 2960 t
(Quicksort\()1440 3100 w
12 I f
(array)1954 3100 w
12 R f
(,)2221 3100 w
12 I f
(start)2281 3100 w
12 R f
(,)2503 3100 w
12 I f
(end)2563 3100 w
12 R f
(\))2736 3100 w
12 B f
(for)1440 3240 w
12 I f
(j)1623 3240 w
12 S f
(=)1717 3240 w
12 R f
(1)1843 3240 w
12 B f
(to)1933 3240 w
12 I f
(p)2063 3240 w
12 S f
(-)2153 3240 w
12 R f
(1)2239 3240 w
12 B f
(do)2329 3240 w
(if)1800 3380 w
12 I f
(j)1904 3380 w
12 S f
(\264)1948 3380 w
12 I f
(rsize)2024 3380 w
12 S f
(\243)2302 3380 w
12 I f
(end)2418 3380 w
12 B f
(then)2621 3380 w
12 I f
(sample)2160 3520 w
12 R f
([)2510 3520 w
12 I f
(i)2560 3520 w
12 S f
(\264)2604 3520 w
12 I f
(p)2680 3520 w
12 S f
(+)2770 3520 w
12 I f
(j)2856 3520 w
12 R f
(])2900 3520 w
12 S f
(=)3010 3520 w
12 I f
(array)3136 3520 w
12 R f
([)3413 3520 w
12 I f
(j)3483 3520 w
12 S f
(\264)3527 3520 w
12 I f
(rsize)3603 3520 w
12 R f
(])3841 3520 w
12 B f
(else)1800 3660 w
12 I f
(sample)2160 3660 w
12 R f
([)2510 3660 w
12 I f
(i)2560 3660 w
12 S f
(\264)2604 3660 w
12 I f
(p)2680 3660 w
12 S f
(+)2770 3660 w
12 I f
(j)2856 3660 w
12 R f
(])2900 3660 w
12 S f
(=)3010 3660 w
12 I f
(array)3136 3660 w
12 R f
([)3413 3660 w
12 I f
(end)3463 3660 w
12 R f
(])3646 3660 w
12 B f
(endfor)1440 3800 w
(endfor)1080 3940 w
12 R f
(# One designated processor sorts the regular sample)7 2499 1 1080 4220 t
12 I f
(sample)3609 4220 w
12 R f
( :)1 84([ 0)1 110 2 3959 4220 t
12 I f
(p)4203 4220 w
12 R f
(\()4273 4220 w
12 I f
(p)4323 4220 w
12 S f
(-)4413 4220 w
12 R f
(1 \))1 110 1 4499 4220 t
12 S f
(-)4629 4220 w
12 R f
(1 ])1 110 1 4715 4220 t
( it chooses)2 508( Then)1 306(# using sequential Quicksort.)3 1403 3 1080 4360 t
12 I f
(p)3327 4360 w
12 S f
(-)3417 4360 w
12 R f
(1 pivots from the sorted)4 1150 1 3503 4360 t
(# regular sample and stores them in)6 1710 1 1080 4500 t
12 I f
(pivots)2820 4500 w
12 R f
([ 1 :)2 154 1 3118 4500 t
12 I f
(p)3282 4500 w
12 S f
(-)3372 4500 w
12 R f
(1 ].)1 140 1 3458 4500 t
(Quicksort\()1080 4640 w
12 I f
(sample)1594 4640 w
12 R f
(, 0,)1 150 1 1934 4640 t
12 I f
(p)2114 4640 w
12 R f
(\()2184 4640 w
12 I f
(p)2234 4640 w
12 S f
(-)2354 4640 w
12 R f
(1 \))1 110 1 2480 4640 t
12 S f
(-)2610 4640 w
12 R f
(1\))2696 4640 w
12 B f
(for)1080 4780 w
12 I f
(i)1263 4780 w
12 S f
(=)1327 4780 w
12 R f
(0)1413 4780 w
12 B f
(to)1503 4780 w
12 I f
(p)1633 4780 w
12 S f
(-)1723 4780 w
12 R f
(2)1809 4780 w
12 B f
(do)1899 4780 w
12 I f
(pivots)1440 4920 w
12 R f
([)1738 4920 w
12 I f
(i)1788 4920 w
12 R f
(])1832 4920 w
12 S f
(=)1942 4920 w
12 I f
(sample)2068 4920 w
12 R f
([)2418 4920 w
12 I f
(i)2468 4920 w
12 S f
(\264)2512 4920 w
12 I f
(p)2588 4920 w
12 S f
(+)2678 4920 w
12 I f
(p /)1 104 1 2764 4920 t
12 R f
(2 ])1 110 1 2878 4920 t
12 B f
(endfor)1080 5060 w
12 R f
(# Divide, in parallel, each sorted list)6 1744 1 1080 5340 t
12 I f
(i)2854 5340 w
12 R f
(into)2918 5340 w
12 I f
(p)3136 5340 w
12 R f
(sublists:)3226 5340 w
(#)1080 5480 w
12 I f
(array)1170 5480 w
12 R f
([)1447 5480 w
12 I f
(subsize)1497 5480 w
12 R f
([)1855 5480 w
12 I f
(i)1905 5480 w
12 S f
(\264)1949 5480 w
12 R f
(\()2025 5480 w
12 I f
(p)2075 5480 w
12 S f
(+)2165 5480 w
12 R f
(1 \))1 110 1 2251 5480 t
12 S f
(+)2381 5480 w
12 I f
(j)2467 5480 w
12 R f
(] :)1 134 1 2511 5480 t
12 I f
(subsize)2695 5480 w
12 R f
([)3053 5480 w
12 I f
(i)3103 5480 w
12 S f
(\264)3147 5480 w
12 R f
(\()3223 5480 w
12 I f
(p)3273 5480 w
12 S f
(+)3363 5480 w
12 R f
(1 \))1 110 1 3449 5480 t
12 S f
(+)3579 5480 w
12 I f
(j)3665 5480 w
12 S f
(+)3719 5480 w
12 R f
(1 ])1 110 1 3805 5480 t
12 S f
(-)3935 5480 w
12 R f
( ,)1 50(1 ])1 110 2 4021 5480 t
(# 0)1 190 1 1080 5620 t
12 S f
(\243)1320 5620 w
12 I f
(j)1446 5620 w
12 S f
(\243)1530 5620 w
12 I f
(p)1646 5620 w
12 S f
(-)1736 5620 w
12 R f
(1, with the chosen pivots as splitters.)6 1772 1 1822 5620 t
12 B f
(for)1080 5760 w
12 I f
(i)1263 5760 w
12 S f
(=)1357 5760 w
12 R f
(0)1483 5760 w
12 B f
(to)1573 5760 w
12 I f
(p)1703 5760 w
12 S f
(-)1793 5760 w
12 R f
(1)1879 5760 w
12 B f
(do in parallel)2 683 1 1969 5760 t
12 I f
(start)1440 5900 w
12 S f
(=)1722 5900 w
12 I f
(i)1848 5900 w
12 S f
(\264)1892 5900 w
12 I f
(size)1968 5900 w
(end)1440 6040 w
12 S f
(=)1673 6040 w
12 R f
(\()1799 6040 w
12 I f
(i)1849 6040 w
12 S f
(+)1913 6040 w
12 R f
(1 \))1 110 1 1999 6040 t
12 S f
(\264)2129 6040 w
12 I f
(size)2205 6040 w
12 S f
(-)2416 6040 w
12 R f
(1 #)1 150 1 2502 6040 t
12 S f
(=)2702 6040 w
12 I f
(start)2828 6040 w
12 S f
(+)3110 6040 w
12 I f
(size)3236 6040 w
12 S f
(-)3477 6040 w
12 R f
(1)3603 6040 w
12 B f
(if)1440 6180 w
12 I f
(end)1544 6180 w
12 S f
(\263)1767 6180 w
12 I f
(n)1883 6180 w
12 B f
(then)1973 6180 w
12 I f
(end)1800 6320 w
12 S f
(=)2033 6320 w
12 I f
(n)2159 6320 w
12 S f
(-)2249 6320 w
12 R f
(1)2335 6320 w
12 I f
(subsize)1440 6460 w
12 R f
([)1798 6460 w
12 I f
(i)1848 6460 w
12 S f
(\264)1892 6460 w
12 R f
(\()1968 6460 w
12 I f
(p)2018 6460 w
12 S f
(+)2108 6460 w
12 R f
(1 \) ])2 160 1 2194 6460 t
12 S f
(=)2424 6460 w
12 I f
(start)2550 6460 w
(subsize)1440 6600 w
12 R f
([)1798 6600 w
12 I f
(i)1848 6600 w
12 S f
(\264)1892 6600 w
12 R f
(\()1968 6600 w
12 I f
(p)2018 6600 w
12 S f
(+)2108 6600 w
12 R f
(1 \))1 110 1 2194 6600 t
12 S f
(+)2324 6600 w
12 I f
(p)2410 6600 w
12 R f
(])2480 6600 w
12 S f
(=)2590 6600 w
12 I f
(end)2716 6600 w
12 S f
(+)2919 6600 w
12 R f
(1)3005 6600 w
(Sublists\()1440 6740 w
12 I f
(array)1863 6740 w
12 R f
(,)2130 6740 w
12 I f
(start)2190 6740 w
12 R f
(,)2412 6740 w
12 I f
(end)2472 6740 w
12 R f
(,)2645 6740 w
12 I f
(subsize)2705 6740 w
12 R f
(,)3053 6740 w
12 I f
(i)3113 6740 w
12 S f
(\264)3157 6740 w
12 R f
(\()3233 6740 w
12 I f
(p)3283 6740 w
12 S f
(+)3373 6740 w
12 R f
(1 \),)1 140 1 3459 6740 t
12 I f
(pivots)3629 6740 w
12 R f
(, 1,)1 150 1 3917 6740 t
12 I f
(p)4097 6740 w
12 S f
(-)4187 6740 w
12 R f
(1\))4273 6740 w
12 B f
(endfor)1080 6880 w
12 R f
(# In parallel, count the size of each of the)9 1988 1 1080 7160 t
12 I f
(p)3098 7160 w
12 R f
(partitions.)3188 7160 w
12 B f
(for)1080 7300 w
12 I f
(i)1263 7300 w
12 S f
(=)1357 7300 w
12 R f
(0)1483 7300 w
12 B f
(to)1573 7300 w
12 I f
(p)1703 7300 w
12 S f
(-)1793 7300 w
12 R f
(1)1879 7300 w
12 B f
(do in parallel)2 683 1 1969 7300 t
cleartomark
showpage
saveobj restore
%%EndPage: 29 29
%%Page: 30 30
/saveobj save def
mark
30 pagesetup
12 R f
(- 30 -)2 260 1 2750 500 t
12 I f
(bucksize)1440 860 w
12 R f
([)1857 860 w
12 I f
(i)1907 860 w
12 R f
(])1951 860 w
12 S f
(=)2061 860 w
12 R f
(0)2187 860 w
12 B f
(for)1440 1000 w
12 I f
(j)1623 1000 w
12 S f
(=)1717 1000 w
12 I f
(i)1843 1000 w
12 B f
(to)1907 1000 w
12 I f
(p)2037 1000 w
12 S f
(\264)2107 1000 w
12 R f
(\()2183 1000 w
12 I f
(p)2233 1000 w
12 S f
(+)2323 1000 w
12 R f
(1 \))1 110 1 2409 1000 t
12 S f
(-)2539 1000 w
12 R f
(1)2625 1000 w
12 B f
(step)2715 1000 w
12 I f
(p)2952 1000 w
12 S f
(+)3042 1000 w
12 R f
(1)3128 1000 w
12 B f
(do)3218 1000 w
12 I f
(bucksize)1800 1140 w
12 R f
([)2217 1140 w
12 I f
(i)2267 1140 w
12 R f
(])2311 1140 w
12 S f
(=)2421 1140 w
12 I f
(bucksize)2547 1140 w
12 R f
([)2964 1140 w
12 I f
(i)3014 1140 w
12 R f
(])3058 1140 w
12 S f
(+)3118 1140 w
12 I f
(subsize)3204 1140 w
12 R f
([)3562 1140 w
12 I f
(j)3632 1140 w
12 S f
(+)3686 1140 w
12 R f
(1 ])1 110 1 3772 1140 t
12 S f
(-)3902 1140 w
12 I f
(subsize)3988 1140 w
12 R f
([)4346 1140 w
12 I f
(j)4416 1140 w
12 R f
(])4460 1140 w
12 B f
(endfor)1440 1280 w
(endfor)1080 1420 w
12 R f
(# In parallel, decide the start-point of each partition in the final array.)12 3333 1 1080 1700 t
12 B f
(for)1080 1840 w
12 I f
(i)1263 1840 w
12 S f
(=)1357 1840 w
12 R f
(1)1483 1840 w
12 B f
(to)1573 1840 w
12 I f
(p)1703 1840 w
12 S f
(-)1793 1840 w
12 R f
(1)1879 1840 w
12 B f
(do in parallel)2 683 1 1969 1840 t
12 I f
(bucksize)1440 1980 w
12 R f
([)1857 1980 w
12 I f
(i)1907 1980 w
12 R f
(])1951 1980 w
12 S f
(=)2061 1980 w
12 I f
(bucksize)2187 1980 w
12 R f
([)2604 1980 w
12 I f
(i)2654 1980 w
12 R f
(])2698 1980 w
12 S f
(+)2758 1980 w
12 I f
(bucksize)2844 1980 w
12 R f
([)3261 1980 w
12 I f
(i)3311 1980 w
12 S f
(-)3375 1980 w
12 R f
(1 ])1 110 1 3461 1980 t
12 B f
(endfor)1080 2120 w
12 I f
(bucksize)1080 2260 w
12 R f
([ 0 ])2 160 1 1497 2260 t
12 S f
(=)1727 2260 w
12 R f
(0)1853 2260 w
(# Merge each partition in parallel.)5 1636 1 1080 2540 t
12 B f
(for)1080 2680 w
12 I f
(i)1263 2680 w
12 S f
(=)1357 2680 w
12 R f
(0)1483 2680 w
12 B f
(to)1573 2680 w
12 I f
(p)1703 2680 w
12 S f
(-)1793 2680 w
12 R f
(1)1879 2680 w
12 B f
(do in parallel)2 683 1 1969 2680 t
12 R f
(merge the following sublists with the standard Mergesort:)7 2784 1 1440 2820 t
12 I f
(array)1440 2960 w
12 R f
([)1717 2960 w
12 I f
(subsize)1767 2960 w
12 R f
([)2125 2960 w
12 I f
(i)2175 2960 w
12 S f
(+)2239 2960 w
12 I f
(j)2325 2960 w
12 S f
(\264)2369 2960 w
12 R f
(\()2445 2960 w
12 I f
(p)2495 2960 w
12 S f
(+)2585 2960 w
12 R f
( :)1 94(1 \) ])2 160 2 2671 2960 t
12 I f
(subsize)2975 2960 w
12 R f
([)3333 2960 w
12 I f
(i)3383 2960 w
12 S f
(+)3447 2960 w
12 I f
(j)3533 2960 w
12 S f
(\264)3577 2960 w
12 R f
(\()3653 2960 w
12 I f
(p)3703 2960 w
12 S f
(+)3793 2960 w
12 R f
(1 \))1 110 1 3879 2960 t
12 S f
(+)4009 2960 w
12 R f
(1 ])1 110 1 4095 2960 t
12 S f
(-)4225 2960 w
12 R f
( 0)1 90(1 ],)1 140 2 4311 2960 t
12 S f
(\243)4591 2960 w
12 I f
(j)4717 2960 w
12 S f
(\243)4801 2960 w
12 I f
(p)4917 2960 w
12 S f
(-)5007 2960 w
12 R f
(1)5093 2960 w
(The merged results are stored in)5 1545 1 1440 3100 t
12 I f
(array)3015 3100 w
12 R f
(starting from index)2 923 1 3312 3100 t
12 I f
(bucksize)4265 3100 w
12 R f
([)4682 3100 w
12 I f
(i)4732 3100 w
12 R f
(])4776 3100 w
12 B f
(endfor)1080 3240 w
(end)720 3380 w
12 R f
(PSRS)937 3380 w
12 B f
(procedure)720 3800 w
12 R f
(Sublists\()1276 3800 w
12 I f
(array)1699 3800 w
12 R f
(,)1966 3800 w
12 I f
(start)2026 3800 w
12 R f
(,)2248 3800 w
12 I f
(end)2308 3800 w
12 R f
(,)2481 3800 w
12 I f
(subsize)2541 3800 w
12 R f
(,)2889 3800 w
12 I f
(at)2949 3800 w
12 R f
(,)3043 3800 w
12 I f
(pivots)3103 3800 w
12 R f
(,)3391 3800 w
12 I f
(f p)1 104 1 3451 3800 t
12 R f
(,)3555 3800 w
12 I f
(lp)3615 3800 w
12 R f
(\))3709 3800 w
(# Recursively divide)2 995 1 720 3940 t
12 I f
(array)1745 3940 w
12 R f
([)2022 3940 w
12 I f
(start)2072 3940 w
12 R f
(:)2304 3940 w
12 I f
(end)2348 3940 w
12 R f
(] into)1 258 1 2531 3940 t
12 I f
(p)2819 3940 w
12 R f
(sublists with)1 607 1 2909 3940 t
12 I f
(pivots)3546 3940 w
12 R f
([)3844 3940 w
12 I f
(f p)1 104 1 3914 3940 t
12 R f
(:)4028 3940 w
12 I f
(lp)4072 3940 w
12 R f
(] as splitters.)2 613 1 4176 3940 t
( are stored in)3 624( sublists)1 423(# The final demarcations for the)5 1545 3 720 4080 t
12 I f
(subsize)3342 4080 w
12 R f
(starting from index)2 923 1 3720 4080 t
12 I f
(at)4673 4080 w
12 R f
(.)4767 4080 w
12 B f
(begin)720 4220 w
12 I f
(mid)1080 4360 w
12 S f
(= \353)1 186 1 1320 4360 t
12 R f
(\()1516 4360 w
12 I f
(f p)1 104 1 1586 4360 t
12 S f
(+)1720 4360 w
12 I f
(lp)1806 4360 w
12 R f
(\))1910 4360 w
12 I f
(/)1960 4360 w
12 R f
(2)2004 4360 w
12 S f
(\373)2074 4360 w
12 I f
(pv)1080 4500 w
12 S f
(=)1253 4500 w
12 I f
(pivot)1379 4500 w
12 R f
([)1630 4500 w
12 I f
(mid)1680 4500 w
12 R f
(])1870 4500 w
12 I f
(lb)1080 4640 w
12 S f
(=)1234 4640 w
12 I f
(start)1360 4640 w
(ub)1080 4780 w
12 S f
(=)1260 4780 w
12 I f
(end)1386 4780 w
12 B f
(while)1080 4920 w
12 I f
(lb)1384 4920 w
12 S f
(\243)1528 4920 w
12 I f
(ub)1644 4920 w
12 B f
(do)1794 4920 w
12 I f
(center)1440 5060 w
12 S f
(= \353)1 186 1 1800 5060 t
12 R f
(\()1996 5060 w
12 I f
(lb)2046 5060 w
12 S f
(+)2170 5060 w
12 I f
(ub)2256 5060 w
12 R f
(\))2386 5060 w
12 I f
(/)2436 5060 w
12 R f
(2)2480 5060 w
12 S f
(\373)2550 5060 w
12 B f
(if)1440 5200 w
12 I f
(array)1544 5200 w
12 R f
([)1821 5200 w
12 I f
(center)1871 5200 w
12 R f
(])2181 5200 w
12 S f
(>)2291 5200 w
12 I f
(pv)2417 5200 w
12 B f
(then)2560 5200 w
12 I f
(ub)1800 5340 w
12 S f
(=)1980 5340 w
12 I f
(center)2106 5340 w
12 S f
(-)2436 5340 w
12 R f
(1)2522 5340 w
12 B f
(else)1440 5480 w
12 I f
(lb)1800 5480 w
12 S f
(=)1954 5480 w
12 I f
(center)2080 5480 w
12 S f
(+)2410 5480 w
12 R f
(1)2496 5480 w
12 B f
(endwhile)1080 5620 w
12 I f
(subsize)1080 5760 w
12 R f
([)1438 5760 w
12 I f
(at)1488 5760 w
12 S f
(+)1612 5760 w
12 I f
(mid)1698 5760 w
12 R f
(])1888 5760 w
12 S f
(=)1998 5760 w
12 I f
(lb)2124 5760 w
12 B f
(if)1080 5900 w
12 I f
(f p)1 104 1 1184 5900 t
12 S f
(<)1348 5900 w
12 I f
(mid)1474 5900 w
12 B f
(then)1684 5900 w
12 R f
(Sublists\()1440 6040 w
12 I f
(array)1863 6040 w
12 R f
(,)2130 6040 w
12 I f
(start)2190 6040 w
12 R f
(,)2412 6040 w
12 I f
(lb)2472 6040 w
12 S f
(-)2596 6040 w
12 R f
(1,)2682 6040 w
12 I f
(subsize at)1 472 1 2802 6040 t
12 R f
(,)3274 6040 w
12 I f
(pivots)3334 6040 w
12 R f
(,)3622 6040 w
12 I f
(f p)1 104 1 3682 6040 t
12 R f
(,)3786 6040 w
12 I f
(mid)3846 6040 w
12 S f
(-)4056 6040 w
12 R f
(1\))4142 6040 w
12 B f
(if)1080 6180 w
12 I f
(mid)1184 6180 w
12 S f
(<)1424 6180 w
12 I f
(lp)1550 6180 w
12 B f
(then)1704 6180 w
12 R f
(Sublists\()1440 6320 w
12 I f
(array)1863 6320 w
12 R f
(,)2130 6320 w
12 I f
(lb)2190 6320 w
12 R f
(,)2284 6320 w
12 I f
(end)2344 6320 w
12 R f
(,)2517 6320 w
12 I f
(subsize)2577 6320 w
12 R f
(,)2925 6320 w
12 I f
(at)2985 6320 w
12 R f
(,)3079 6320 w
12 I f
(pivots)3139 6320 w
12 R f
(,)3427 6320 w
12 I f
(mid)3487 6320 w
12 S f
(+)3697 6320 w
12 R f
(1,)3783 6320 w
12 I f
(lp)3903 6320 w
12 R f
(\))3997 6320 w
12 B f
(end)720 6460 w
12 R f
(Sublists)937 6460 w
cleartomark
showpage
saveobj restore
%%EndPage: 30 30
%%Page: 31 31
/saveobj save def
mark
31 pagesetup
12 R f
(- 31 -)2 260 1 2750 500 t
12 B f
( example.)1 487( PSRS)1 353(FIG. 1.)1 364 3 2278 6040 t
cleartomark
showpage
saveobj restore
%%EndPage: 31 31
%%Page: 32 32
/saveobj save def
mark
32 pagesetup
12 R f
(- 32 -)2 260 1 2750 500 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 810 t
12 R f
(Sorting Times)1 686 1 2836 950 t
12 I f
(\(in seconds\))1 584 1 2887 1090 t
12 S f
(_ ______________________________________________________)1 3281 1 1529 1110 t
12 R f
(Sizes)1092 1100 w
( 32PEs 64PEs)2 974( 16PEs)1 499( 4PEs 8PEs)2 900(1PE 2PEs)1 703 4 1674 1250 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1260 t
(_ ________________________________________________________________)1 3861 1 949 1280 t
12 R f
( 1.09 1.66)2 974( 1.06)1 468( 3.86 2.14 1.56)3 1350(100000 6.63)1 870 4 1069 1410 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1430 t
12 R f
( 1.43 1.83)2 974( 1.71)1 468(200000 14.00 8.08 4.20 2.74)4 2220 3 1069 1570 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1590 t
12 R f
(400000)1069 1730 w
12 I f
(29.71)1669 1730 w
12 R f
( 2.11 2.20)2 974( 3.13)1 468(16.77 8.60 5.58)2 1170 3 2119 1730 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1750 t
12 R f
(800000)1069 1890 w
12 I f
(62.62)1669 1890 w
12 R f
( 3.50 2.86)2 974( 5.84)1 468( 10.67)1 450(- 21.51)1 605 4 2234 1890 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1910 t
12 R f
(1000000)1009 2050 w
12 I f
(79.56)1669 2050 w
12 R f
( 4.38 3.12)2 974( 6.97)1 468( 13.13)1 450(- 29.88)1 605 4 2234 2050 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 2070 t
12 R f
(2000000)1009 2210 w
12 I f
(167.10)1609 2210 w
12 R f
( 7.87 5.19)2 974( 13.73)1 583(- - -)2 940 3 2234 2210 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 2230 t
12 R f
(4000000)1009 2370 w
12 I f
(350.17)1609 2370 w
12 R f
( 8.70)1 487( 14.83)1 602( -)1 468(- - -)2 940 4 2234 2370 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 2390 t
12 R f
(8000000)1009 2530 w
12 I f
(732.28)1609 2530 w
12 R f
( 16.49)1 602( -)1 487( -)1 468(- - -)2 940 4 2234 2530 t
12 S f
( \347)1 -3861(_ ________________________________________________________________)1 3861 2 949 2550 t
(\347)949 2490 w
(\347)949 2370 w
(\347)949 2250 w
(\347)949 2130 w
(\347)949 2010 w
(\347)949 1890 w
(\347)949 1770 w
(\347)949 1650 w
(\347)949 1530 w
(\347)949 1410 w
(\347)949 1290 w
(\347)949 1170 w
(\347)949 1050 w
(\347)949 930 w
(\347)1509 2550 w
(\347)1509 2490 w
(\347)1509 2370 w
(\347)1509 2250 w
(\347)1509 2130 w
(\347)1509 2010 w
(\347)1509 1890 w
(\347)1509 1770 w
(\347)1509 1650 w
(\347)1509 1530 w
(\347)1509 1410 w
(\347)1509 1290 w
(\347)1509 1170 w
(\347)1509 1050 w
(\347)1509 930 w
(\347)1529 2550 w
(\347)1529 2490 w
(\347)1529 2370 w
(\347)1529 2250 w
(\347)1529 2130 w
(\347)1529 2010 w
(\347)1529 1890 w
(\347)1529 1770 w
(\347)1529 1650 w
(\347)1529 1530 w
(\347)1529 1410 w
(\347)1529 1290 w
(\347)1529 1170 w
(\347)1529 1050 w
(\347)1529 930 w
(\347)2029 2550 w
(\347)2029 2430 w
(\347)2029 2310 w
(\347)2029 2190 w
(\347)2029 2070 w
(\347)2029 1950 w
(\347)2029 1830 w
(\347)2029 1710 w
(\347)2029 1590 w
(\347)2029 1470 w
(\347)2029 1350 w
(\347)2029 1230 w
(\347)2479 2550 w
(\347)2479 2430 w
(\347)2479 2310 w
(\347)2479 2190 w
(\347)2479 2070 w
(\347)2479 1950 w
(\347)2479 1830 w
(\347)2479 1710 w
(\347)2479 1590 w
(\347)2479 1470 w
(\347)2479 1350 w
(\347)2479 1230 w
(\347)2929 2550 w
(\347)2929 2430 w
(\347)2929 2310 w
(\347)2929 2190 w
(\347)2929 2070 w
(\347)2929 1950 w
(\347)2929 1830 w
(\347)2929 1710 w
(\347)2929 1590 w
(\347)2929 1470 w
(\347)2929 1350 w
(\347)2929 1230 w
(\347)3379 2550 w
(\347)3379 2430 w
(\347)3379 2310 w
(\347)3379 2190 w
(\347)3379 2070 w
(\347)3379 1950 w
(\347)3379 1830 w
(\347)3379 1710 w
(\347)3379 1590 w
(\347)3379 1470 w
(\347)3379 1350 w
(\347)3379 1230 w
(\347)3866 2550 w
(\347)3866 2430 w
(\347)3866 2310 w
(\347)3866 2190 w
(\347)3866 2070 w
(\347)3866 1950 w
(\347)3866 1830 w
(\347)3866 1710 w
(\347)3866 1590 w
(\347)3866 1470 w
(\347)3866 1350 w
(\347)3866 1230 w
(\347)4353 2550 w
(\347)4353 2430 w
(\347)4353 2310 w
(\347)4353 2190 w
(\347)4353 2070 w
(\347)4353 1950 w
(\347)4353 1830 w
(\347)4353 1710 w
(\347)4353 1590 w
(\347)4353 1470 w
(\347)4353 1350 w
(\347)4353 1230 w
(\347)4810 2550 w
(\347)4810 2490 w
(\347)4810 2370 w
(\347)4810 2250 w
(\347)4810 2130 w
(\347)4810 2010 w
(\347)4810 1890 w
(\347)4810 1770 w
(\347)4810 1650 w
(\347)4810 1530 w
(\347)4810 1410 w
(\347)4810 1290 w
(\347)4810 1170 w
(\347)4810 1050 w
(\347)4810 930 w
12 B f
(Table 1. Sorting times of PSRS.)5 1612 1 2074 2900 t
cleartomark
showpage
saveobj restore
%%EndPage: 32 32
%%Page: 33 33
/saveobj save def
mark
33 pagesetup
12 R f
(- 33 -)2 260 1 2750 500 t
cleartomark
saveobj restore
%%BeginGlobal
%
% Version 3.3 drawing procedures for dpost. Automatically pulled in, but only
% when needed.
%

/inpath false def
/savematrix matrix def

/Dl {
	inpath
		{pop pop neg lineto}
		{newpath neg moveto neg lineto stroke}
	ifelse
} bind def

/De {
	/y1 exch 2 div def
	/x1 exch 2 div def
	/savematrix savematrix currentmatrix def
	neg exch x1 add exch translate
	x1 y1 scale
	0 0 1 0 360
	inpath
		{1 0 moveto arc savematrix setmatrix}
		{newpath arc savematrix setmatrix stroke}
	ifelse
} bind def

/Da {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arc}
		{newpath arc stroke}
	ifelse
} bind def

/DA {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arcn}
		{newpath arcn stroke}
	ifelse
} bind def

/Ds {
	/y2 exch def
	/x2 exch def
	/y1 exch def
	/x1 exch def
	/y0 exch def
	/x0 exch def
	x0 5 x1 mul add 6 div
	y0 5 y1 mul add -6 div
	x2 5 x1 mul add 6 div
	y2 5 y1 mul add -6 div
	x1 x2 add 2 div
	y1 y2 add -2 div
	inpath
		{curveto}
		{newpath x0 x1 add 2 div y0 y1 add -2 div moveto curveto stroke}
	ifelse
} bind def
%%EndGlobal
/saveobj save def
mark
24 R f
4319 3469 1759 3469 Dl
1759 909 1759 3469 Dl
12 R f
(Speedup)1027 2213 w
(PEs)2946 3813 w
24 R f
1759 3513 1759 3469 Dl
12 R f
(0)1729 3620 w
24 R f
2272 3513 2272 3469 Dl
12 R f
(16)2212 3620 w
24 R f
2784 3513 2784 3469 Dl
12 R f
(32)2724 3620 w
24 R f
3296 3513 3296 3469 Dl
12 R f
(48)3236 3620 w
24 R f
3808 3513 3808 3469 Dl
12 R f
(64)3748 3620 w
24 R f
1715 3469 1759 3469 Dl
12 R f
(0)1642 3493 w
24 R f
1715 2956 1759 2956 Dl
12 R f
(16)1582 2980 w
24 R f
1715 2444 1759 2444 Dl
12 R f
(32)1582 2468 w
24 R f
1715 1932 1759 1932 Dl
12 R f
(48)1582 1956 w
24 R f
1715 1420 1759 1420 Dl
12 R f
(64)1582 1444 w
9 R f
(.)1780 3439 w
(.)1802 3417 w
(.)1825 3394 w
(.)1847 3372 w
(.)1870 3349 w
(.)1893 3326 w
(.)1916 3303 w
(.)1938 3281 w
(.)1961 3258 w
(.)1983 3236 w
(.)2006 3213 w
(.)2029 3190 w
(.)2051 3168 w
(.)2074 3145 w
(.)2096 3123 w
(.)2119 3100 w
(.)2142 3077 w
(.)2165 3054 w
(.)2187 3032 w
(.)2210 3009 w
(.)2232 2987 w
(.)2256 2964 w
(.)2278 2941 w
(.)2300 2919 w
(.)2323 2896 w
(.)2346 2874 w
(.)2369 2850 w
(.)2391 2828 w
(.)2414 2805 w
(.)2436 2783 w
(.)2459 2760 w
(.)2482 2737 w
(.)2505 2714 w
(.)2527 2692 w
(.)2550 2669 w
(.)2572 2647 w
(.)2595 2624 w
(.)2618 2601 w
(.)2640 2579 w
(.)2663 2556 w
(.)2685 2534 w
(.)2708 2511 w
(.)2731 2488 w
(.)2754 2465 w
(.)2776 2443 w
(.)2799 2420 w
(.)2821 2398 w
(.)2844 2375 w
(.)2867 2352 w
(.)2889 2330 w
(.)2912 2307 w
(.)2934 2285 w
(.)2958 2262 w
(.)2980 2239 w
(.)3003 2216 w
(.)3025 2194 w
(.)3048 2171 w
(.)3071 2148 w
(.)3094 2125 w
(.)3116 2103 w
(.)3139 2080 w
(.)3161 2058 w
(.)3184 2035 w
(.)3207 2012 w
(.)3229 1990 w
(.)3252 1967 w
(.)3274 1945 w
(.)3297 1922 w
(.)3320 1899 w
(.)3343 1876 w
(.)3365 1854 w
(.)3388 1831 w
(.)3410 1809 w
(.)3433 1786 w
(.)3456 1763 w
(.)3478 1741 w
(.)3501 1718 w
(.)3523 1696 w
(.)3546 1673 w
(.)3569 1650 w
(.)3592 1627 w
(.)3614 1605 w
(.)3637 1582 w
(.)3660 1560 w
(.)3683 1536 w
(.)3705 1514 w
(.)3728 1491 w
(.)3750 1469 w
(.)3773 1446 w
(.)3796 1423 w
12 R f
(* linear)1 364 1 3808 1444 t
9 R f
(.)1780 3439 w
(. .)1 23 1 1811 3416 t
(.)1844 3395 w
(. .)1 23 1 1875 3372 t
(.)1908 3364 w
(.)1939 3354 w
(.)1972 3345 w
(. .)1 23 1 2004 3336 t
(.)2035 3328 w
(.)2068 3320 w
(.)2099 3312 w
(.)2132 3304 w
(.)2163 3295 w
(.)2196 3288 w
(.)2227 3280 w
( .)1 33( .)1 31( .)1 32(. .)1 23 4 2260 3272 t
(. .)1 56 1 2387 3273 t
(. .)1 56 1 2451 3274 t
( .)1 33( .)1 31( .)1 32(. .)1 56 4 2515 3275 t
(. .)1 56 1 2675 3276 t
( .)1 0(. .)1 56 2 2739 3277 t
(.)2803 3279 w
(.)2836 3281 w
(.)2868 3283 w
(.)2899 3285 w
(.)2932 3288 w
(.)2963 3290 w
(.)2996 3292 w
(.)3027 3293 w
(.)3060 3295 w
(.)3091 3298 w
(.)3124 3300 w
(.)3156 3302 w
(.)3187 3304 w
(.)3220 3306 w
(.)3251 3308 w
(.)3284 3311 w
(.)3315 3312 w
(.)3348 3314 w
(.)3379 3316 w
(.)3412 3318 w
(.)3444 3321 w
(.)3475 3323 w
(.)3508 3325 w
(.)3539 3327 w
(.)3572 3329 w
(.)3603 3331 w
(.)3636 3333 w
(.)3667 3335 w
(.)3700 3337 w
(.)3732 3339 w
(.)3763 3342 w
(.)3796 3344 w
12 R f
(* 100,000)1 540 1 3808 3365 t
1823 3413 1792 3436 Dl
1848 3393 1823 3413 Dl
1888 3362 1863 3382 Dl
1916 3350 1887 3362 Dl
1966 3328 1937 3340 Dl
2015 3306 1986 3318 Dl
2045 3294 2016 3305 Dl
2101 3273 2072 3284 Dl
2158 3250 2129 3261 Dl
2214 3229 2185 3240 Dl
2271 3207 2242 3218 Dl
2303 3205 2272 3207 Dl
2363 3199 2332 3201 Dl
2422 3193 2391 3195 Dl
2483 3187 2452 3189 Dl
2543 3181 2512 3183 Dl
2602 3175 2571 3177 Dl
2663 3169 2632 3171 Dl
2723 3164 2692 3166 Dl
2782 3158 2751 3160 Dl
2815 3158 2784 3156 Dl
2877 3163 2846 3161 Dl
2939 3167 2908 3165 Dl
3001 3171 2970 3169 Dl
3062 3175 3031 3173 Dl
3124 3179 3093 3177 Dl
3186 3183 3155 3181 Dl
3248 3187 3217 3185 Dl
3311 3191 3280 3189 Dl
3373 3195 3342 3193 Dl
3435 3199 3404 3197 Dl
3497 3204 3466 3202 Dl
3559 3207 3528 3205 Dl
3620 3212 3589 3210 Dl
3682 3216 3651 3214 Dl
3744 3220 3713 3218 Dl
3807 3224 3776 3222 Dl
(* 200,000)1 540 1 3808 3248 t
1823 3412 1792 3436 Dl
1887 3358 1823 3412 Dl
2015 3298 1887 3358 Dl
2272 3165 2016 3298 Dl
2783 3020 2272 3164 Dl
3807 3035 2784 3020 Dl
(* 400,000)1 540 1 3808 3060 t
9 R f
(.)1780 3439 w
(.)1803 3424 w
(.)1828 3409 w
(.)1852 3393 w
(. .)1 23 1 1875 3378 t
(.)1901 3360 w
(.)1926 3341 w
(.)1952 3321 w
(.)1978 3303 w
(. .)1 23 1 2004 3284 t
(.)2032 3267 w
(.)2060 3249 w
(.)2089 3232 w
(.)2117 3215 w
(.)2146 3198 w
(.)2174 3180 w
(.)2203 3163 w
(.)2231 3146 w
(. .)1 23 1 2260 3128 t
(.)2288 3115 w
(.)2317 3102 w
(.)2345 3090 w
(.)2374 3077 w
(.)2402 3064 w
(.)2430 3051 w
(.)2459 3038 w
(.)2487 3026 w
(.)2515 3013 w
(.)2544 3000 w
(.)2572 2987 w
(.)2601 2975 w
(.)2629 2962 w
(.)2658 2949 w
(.)2686 2936 w
(.)2715 2924 w
(.)2743 2911 w
(. .)1 23 1 2772 2898 t
(.)2803 2894 w
(.)2836 2890 w
(.)2868 2886 w
(.)2899 2882 w
(.)2932 2879 w
(.)2963 2874 w
(.)2996 2871 w
(.)3027 2866 w
(.)3060 2863 w
(.)3091 2858 w
(.)3124 2855 w
(.)3156 2850 w
(.)3187 2847 w
(.)3220 2843 w
(.)3251 2839 w
(.)3284 2835 w
(.)3315 2831 w
(.)3348 2827 w
(.)3379 2823 w
(.)3412 2819 w
(.)3444 2815 w
(.)3475 2811 w
(.)3508 2807 w
(.)3539 2803 w
(.)3572 2799 w
(.)3603 2795 w
(.)3636 2791 w
(.)3667 2787 w
(.)3700 2784 w
(.)3732 2779 w
(.)3763 2776 w
(.)3796 2771 w
12 R f
(* 800,000)1 540 1 3808 2792 t
1820 3421 1792 3436 Dl
1887 3384 1859 3399 Dl
1911 3363 1887 3383 Dl
1963 3319 1939 3339 Dl
2015 3275 1991 3295 Dl
2042 3256 2016 3274 Dl
2099 3218 2073 3236 Dl
2156 3179 2130 3197 Dl
2214 3141 2188 3159 Dl
2271 3103 2245 3121 Dl
2301 3091 2272 3103 Dl
2361 3066 2332 3078 Dl
2421 3040 2392 3052 Dl
2482 3015 2453 3027 Dl
2542 2990 2513 3002 Dl
2602 2964 2573 2976 Dl
2662 2938 2633 2950 Dl
2723 2913 2694 2925 Dl
2783 2887 2754 2899 Dl
2814 2880 2784 2887 Dl
2876 2866 2846 2873 Dl
2938 2852 2908 2859 Dl
3000 2838 2970 2845 Dl
3061 2823 3031 2830 Dl
3124 2809 3094 2816 Dl
3186 2795 3156 2802 Dl
3248 2781 3218 2788 Dl
3310 2766 3280 2773 Dl
3372 2752 3342 2759 Dl
3434 2738 3404 2745 Dl
3496 2724 3466 2731 Dl
3558 2709 3528 2716 Dl
3620 2695 3590 2702 Dl
3682 2681 3652 2688 Dl
3744 2667 3714 2674 Dl
3807 2653 3777 2660 Dl
(* 1,000,000)1 570 1 3808 2676 t
2272 3079 1792 3436 Dl
2783 2790 2272 3079 Dl
3807 2438 2784 2789 Dl
(* 2,000,000)1 570 1 3808 2463 t
9 R f
(.)1780 3439 w
(.)1806 3421 w
(.)1831 3401 w
(.)1858 3383 w
(.)1884 3363 w
(.)1910 3344 w
(.)1936 3325 w
(.)1962 3306 w
(.)1988 3288 w
(.)2014 3268 w
(.)2040 3249 w
(.)2067 3230 w
(.)2093 3211 w
(.)2119 3192 w
(.)2145 3173 w
(.)2171 3154 w
(.)2197 3135 w
(.)2223 3116 w
(.)2250 3097 w
(.)2276 3078 w
(.)2302 3059 w
(.)2328 3040 w
(.)2354 3020 w
(.)2380 3002 w
(.)2406 2982 w
(.)2432 2964 w
(.)2459 2945 w
(.)2484 2925 w
(.)2510 2907 w
(.)2536 2887 w
(.)2563 2868 w
(.)2589 2849 w
(.)2615 2830 w
(.)2641 2811 w
(.)2667 2792 w
(.)2693 2773 w
(.)2719 2754 w
(.)2745 2735 w
(. .)1 23 1 2772 2716 t
(.)2800 2701 w
(.)2829 2686 w
(.)2857 2672 w
(.)2886 2657 w
(.)2914 2642 w
(.)2942 2627 w
(.)2970 2613 w
(.)2999 2598 w
(.)3027 2583 w
(.)3056 2568 w
(.)3084 2554 w
(.)3113 2539 w
(.)3141 2524 w
(.)3170 2509 w
(.)3198 2494 w
(.)3227 2480 w
(.)3255 2465 w
(.)3284 2450 w
(.)3312 2435 w
(.)3341 2421 w
(.)3369 2406 w
(.)3397 2391 w
(.)3426 2376 w
(.)3454 2362 w
(.)3482 2346 w
(.)3511 2332 w
(.)3539 2317 w
(.)3568 2303 w
(.)3596 2287 w
(.)3625 2273 w
(.)3653 2258 w
(.)3682 2244 w
(.)3710 2228 w
(.)3739 2214 w
(.)3767 2199 w
(.)3796 2184 w
12 R f
(* 4,000,000)1 570 1 3808 2205 t
(* 8,000,000)1 570 1 3808 2071 t
12 B f
(FIG. 2. Speedups of PSRS.)4 1365 1 2197 4160 t
cleartomark
showpage
saveobj restore
%%EndPage: 33 33
%%Page: 34 34
/saveobj save def
mark
34 pagesetup
12 R f
(- 34 -)2 260 1 2750 500 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 810 t
12 R f
(Sorting Times)1 686 1 2836 950 t
12 I f
(\(in seconds\))1 584 1 2887 1090 t
12 S f
(_ ______________________________________________________)1 3281 1 1529 1110 t
12 R f
(Sizes)1092 1100 w
( 32PEs 64PEs)2 974( 16PEs)1 499( 4PEs 8PEs)2 900(1PE 2PEs)1 703 4 1674 1250 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1260 t
(_ ________________________________________________________________)1 3861 1 949 1280 t
12 R f
( 1.97 2.34)2 974( 1.80)1 468( 4.33 2.44 2.00)3 1350(100000 6.63)1 870 4 1069 1410 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1430 t
12 R f
( 2.72 3.00)2 974( 2.60)1 468(200000 14.00 8.87 4.78 3.35)4 2220 3 1069 1570 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1590 t
12 R f
(400000)1069 1730 w
12 I f
(29.71)1669 1730 w
12 R f
( 3.91 4.34)2 974( 4.33)1 468(19.34 9.67 6.26)2 1170 3 2119 1730 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1750 t
12 R f
(800000)1069 1890 w
12 I f
(62.62)1669 1890 w
12 R f
( 6.01 6.57)2 974( 7.15)1 468( 12.14)1 450(- 24.27)1 605 4 2234 1890 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 1910 t
12 R f
(1000000)1009 2050 w
12 I f
(79.56)1669 2050 w
12 R f
( 6.96 7.28)2 974( 8.75)1 468( 16.54)1 450(- 33.86)1 605 4 2234 2050 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 2070 t
12 R f
(2000000)1009 2210 w
12 I f
(167.10)1609 2210 w
12 R f
( 11.09 10.95)2 974( 18.39)1 583(- - -)2 940 3 2234 2210 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 2230 t
12 R f
(4000000)1009 2370 w
12 I f
(350.17)1609 2370 w
12 R f
( 15.83)1 487( 22.10)1 602( -)1 468(- - -)2 940 4 2234 2370 t
12 S f
(_ ________________________________________________________________)1 3861 1 949 2390 t
12 R f
(8000000)1009 2530 w
12 I f
(732.28)1609 2530 w
12 R f
( -)1 487( -)1 468(- - -)2 940 3 2234 2530 t
12 S f
( \347)1 -3861(_ ________________________________________________________________)1 3861 2 949 2550 t
(\347)949 2490 w
(\347)949 2370 w
(\347)949 2250 w
(\347)949 2130 w
(\347)949 2010 w
(\347)949 1890 w
(\347)949 1770 w
(\347)949 1650 w
(\347)949 1530 w
(\347)949 1410 w
(\347)949 1290 w
(\347)949 1170 w
(\347)949 1050 w
(\347)949 930 w
(\347)1509 2550 w
(\347)1509 2490 w
(\347)1509 2370 w
(\347)1509 2250 w
(\347)1509 2130 w
(\347)1509 2010 w
(\347)1509 1890 w
(\347)1509 1770 w
(\347)1509 1650 w
(\347)1509 1530 w
(\347)1509 1410 w
(\347)1509 1290 w
(\347)1509 1170 w
(\347)1509 1050 w
(\347)1509 930 w
(\347)1529 2550 w
(\347)1529 2490 w
(\347)1529 2370 w
(\347)1529 2250 w
(\347)1529 2130 w
(\347)1529 2010 w
(\347)1529 1890 w
(\347)1529 1770 w
(\347)1529 1650 w
(\347)1529 1530 w
(\347)1529 1410 w
(\347)1529 1290 w
(\347)1529 1170 w
(\347)1529 1050 w
(\347)1529 930 w
(\347)2029 2550 w
(\347)2029 2430 w
(\347)2029 2310 w
(\347)2029 2190 w
(\347)2029 2070 w
(\347)2029 1950 w
(\347)2029 1830 w
(\347)2029 1710 w
(\347)2029 1590 w
(\347)2029 1470 w
(\347)2029 1350 w
(\347)2029 1230 w
(\347)2479 2550 w
(\347)2479 2430 w
(\347)2479 2310 w
(\347)2479 2190 w
(\347)2479 2070 w
(\347)2479 1950 w
(\347)2479 1830 w
(\347)2479 1710 w
(\347)2479 1590 w
(\347)2479 1470 w
(\347)2479 1350 w
(\347)2479 1230 w
(\347)2929 2550 w
(\347)2929 2430 w
(\347)2929 2310 w
(\347)2929 2190 w
(\347)2929 2070 w
(\347)2929 1950 w
(\347)2929 1830 w
(\347)2929 1710 w
(\347)2929 1590 w
(\347)2929 1470 w
(\347)2929 1350 w
(\347)2929 1230 w
(\347)3379 2550 w
(\347)3379 2430 w
(\347)3379 2310 w
(\347)3379 2190 w
(\347)3379 2070 w
(\347)3379 1950 w
(\347)3379 1830 w
(\347)3379 1710 w
(\347)3379 1590 w
(\347)3379 1470 w
(\347)3379 1350 w
(\347)3379 1230 w
(\347)3866 2550 w
(\347)3866 2430 w
(\347)3866 2310 w
(\347)3866 2190 w
(\347)3866 2070 w
(\347)3866 1950 w
(\347)3866 1830 w
(\347)3866 1710 w
(\347)3866 1590 w
(\347)3866 1470 w
(\347)3866 1350 w
(\347)3866 1230 w
(\347)4353 2550 w
(\347)4353 2430 w
(\347)4353 2310 w
(\347)4353 2190 w
(\347)4353 2070 w
(\347)4353 1950 w
(\347)4353 1830 w
(\347)4353 1710 w
(\347)4353 1590 w
(\347)4353 1470 w
(\347)4353 1350 w
(\347)4353 1230 w
(\347)4810 2550 w
(\347)4810 2490 w
(\347)4810 2370 w
(\347)4810 2250 w
(\347)4810 2130 w
(\347)4810 2010 w
(\347)4810 1890 w
(\347)4810 1770 w
(\347)4810 1650 w
(\347)4810 1530 w
(\347)4810 1410 w
(\347)4810 1290 w
(\347)4810 1170 w
(\347)4810 1050 w
(\347)4810 930 w
12 B f
(Table 2. Sorting times of PSS.)5 1526 1 2117 2900 t
cleartomark
showpage
saveobj restore
%%EndPage: 34 34
%%Page: 35 35
/saveobj save def
mark
35 pagesetup
12 R f
(- 35 -)2 260 1 2750 500 t
24 R f
4319 3469 1759 3469 Dl
1759 909 1759 3469 Dl
12 R f
(Speedup)1027 2213 w
(PEs)2946 3813 w
24 R f
1759 3513 1759 3469 Dl
12 R f
(0)1729 3620 w
24 R f
2272 3513 2272 3469 Dl
12 R f
(16)2212 3620 w
24 R f
2784 3513 2784 3469 Dl
12 R f
(32)2724 3620 w
24 R f
3296 3513 3296 3469 Dl
12 R f
(48)3236 3620 w
24 R f
3808 3513 3808 3469 Dl
12 R f
(64)3748 3620 w
24 R f
1715 3469 1759 3469 Dl
12 R f
(0)1642 3493 w
24 R f
1715 2956 1759 2956 Dl
12 R f
(16)1582 2980 w
24 R f
1715 2444 1759 2444 Dl
12 R f
(32)1582 2468 w
24 R f
1715 1932 1759 1932 Dl
12 R f
(48)1582 1956 w
24 R f
1715 1420 1759 1420 Dl
12 R f
(64)1582 1444 w
9 R f
(.)1780 3439 w
(.)1802 3417 w
(.)1825 3394 w
(.)1847 3372 w
(.)1870 3349 w
(.)1893 3326 w
(.)1916 3303 w
(.)1938 3281 w
(.)1961 3258 w
(.)1983 3236 w
(.)2006 3213 w
(.)2029 3190 w
(.)2051 3168 w
(.)2074 3145 w
(.)2096 3123 w
(.)2119 3100 w
(.)2142 3077 w
(.)2165 3054 w
(.)2187 3032 w
(.)2210 3009 w
(.)2232 2987 w
(.)2256 2964 w
(.)2278 2941 w
(.)2300 2919 w
(.)2323 2896 w
(.)2346 2874 w
(.)2369 2850 w
(.)2391 2828 w
(.)2414 2805 w
(.)2436 2783 w
(.)2459 2760 w
(.)2482 2737 w
(.)2505 2714 w
(.)2527 2692 w
(.)2550 2669 w
(.)2572 2647 w
(.)2595 2624 w
(.)2618 2601 w
(.)2640 2579 w
(.)2663 2556 w
(.)2685 2534 w
(.)2708 2511 w
(.)2731 2488 w
(.)2754 2465 w
(.)2776 2443 w
(.)2799 2420 w
(.)2821 2398 w
(.)2844 2375 w
(.)2867 2352 w
(.)2889 2330 w
(.)2912 2307 w
(.)2934 2285 w
(.)2958 2262 w
(.)2980 2239 w
(.)3003 2216 w
(.)3025 2194 w
(.)3048 2171 w
(.)3071 2148 w
(.)3094 2125 w
(.)3116 2103 w
(.)3139 2080 w
(.)3161 2058 w
(.)3184 2035 w
(.)3207 2012 w
(.)3229 1990 w
(.)3252 1967 w
(.)3274 1945 w
(.)3297 1922 w
(.)3320 1899 w
(.)3343 1876 w
(.)3365 1854 w
(.)3388 1831 w
(.)3410 1809 w
(.)3433 1786 w
(.)3456 1763 w
(.)3478 1741 w
(.)3501 1718 w
(.)3523 1696 w
(.)3546 1673 w
(.)3569 1650 w
(.)3592 1627 w
(.)3614 1605 w
(.)3637 1582 w
(.)3660 1560 w
(.)3683 1536 w
(.)3705 1514 w
(.)3728 1491 w
(.)3750 1469 w
(.)3773 1446 w
(.)3796 1423 w
12 R f
(* linear)1 364 1 3808 1444 t
9 R f
(.)1780 3439 w
(. .)1 23 1 1811 3423 t
(.)1844 3403 w
(. .)1 23 1 1875 3385 t
(.)1908 3380 w
(.)1939 3375 w
(.)1972 3370 w
(. .)1 23 1 2004 3365 t
(.)2035 3364 w
(.)2068 3362 w
(.)2099 3361 w
(.)2132 3360 w
(.)2163 3358 w
(.)2196 3357 w
(.)2227 3355 w
( .)1 32(. .)1 23 2 2260 3354 t
(.)2323 3355 w
(. .)1 54 1 2356 3356 t
(. .)1 54 1 2420 3357 t
(.)2484 3358 w
(.)2515 3359 w
( .)1 31(. .)1 55 2 2548 3360 t
(.)2644 3361 w
(. .)1 56 1 2675 3362 t
(.)2739 3363 w
(. .)1 23 1 2772 3364 t
( .)1 32(. .)1 56 2 2803 3365 t
(.)2899 3366 w
( .)1 33(. .)1 54 2 2932 3367 t
(.)3027 3368 w
(. .)1 54 1 3060 3369 t
(. .)1 55 1 3124 3370 t
(. .)1 56 1 3187 3371 t
(. .)1 56 1 3251 3372 t
(. .)1 56 1 3315 3373 t
(.)3379 3374 w
( .)1 31(. .)1 55 2 3412 3375 t
(.)3508 3376 w
(.)3539 3377 w
( .)1 33(. .)1 54 2 3572 3378 t
(.)3667 3379 w
( .)1 31(. .)1 55 2 3700 3380 t
(.)3796 3381 w
12 R f
(* 100,000)1 540 1 3808 3415 t
1823 3418 1792 3436 Dl
1849 3400 1823 3418 Dl
1887 3375 1861 3393 Dl
1917 3366 1887 3375 Dl
1966 3350 1936 3359 Dl
2015 3335 1985 3344 Dl
2047 3330 2016 3335 Dl
2103 3321 2072 3326 Dl
2159 3313 2128 3318 Dl
2215 3305 2184 3310 Dl
2271 3296 2240 3301 Dl
2303 3296 2272 3296 Dl
2363 3297 2332 3297 Dl
2422 3298 2391 3298 Dl
2483 3299 2452 3299 Dl
2543 3300 2512 3300 Dl
2602 3300 2571 3300 Dl
2663 3302 2632 3302 Dl
2723 3303 2692 3303 Dl
2782 3303 2751 3303 Dl
2815 3304 2784 3304 Dl
2877 3305 2846 3305 Dl
2939 3305 2908 3305 Dl
3001 3307 2970 3307 Dl
3062 3308 3031 3308 Dl
3124 3308 3093 3308 Dl
3186 3309 3155 3309 Dl
3248 3310 3217 3310 Dl
3311 3311 3280 3311 Dl
3373 3312 3342 3312 Dl
3435 3313 3404 3313 Dl
3497 3314 3466 3314 Dl
3559 3315 3528 3315 Dl
3620 3315 3589 3315 Dl
3682 3317 3651 3317 Dl
3744 3318 3713 3318 Dl
3806 3318 3775 3318 Dl
(* 200,000)1 540 1 3808 3343 t
1823 3419 1792 3436 Dl
1887 3371 1823 3419 Dl
2015 3316 1887 3370 Dl
2272 3249 2016 3316 Dl
2783 3226 2272 3249 Dl
3807 3248 2784 3225 Dl
(* 400,000)1 540 1 3808 3267 t
9 R f
(.)1780 3439 w
(.)1811 3423 w
(.)1844 3406 w
(. .)1 23 1 1875 3389 t
(.)1901 3372 w
(.)1926 3356 w
(.)1952 3339 w
(.)1978 3323 w
(. .)1 23 1 2004 3306 t
(.)2032 3293 w
(.)2060 3281 w
(.)2089 3268 w
(.)2117 3255 w
(.)2146 3242 w
(.)2174 3230 w
(.)2203 3217 w
(.)2231 3204 w
(. .)1 23 1 2260 3191 t
(.)2292 3188 w
(.)2323 3185 w
(.)2356 3181 w
(.)2387 3178 w
(.)2420 3174 w
(.)2451 3172 w
(.)2484 3168 w
(.)2515 3164 w
(.)2548 3162 w
(.)2580 3158 w
(.)2611 3154 w
(.)2644 3151 w
(.)2675 3148 w
(.)2708 3145 w
(.)2739 3141 w
(. .)1 23 1 2772 3138 t
(.)2803 3139 w
(.)2836 3140 w
(. .)1 54 1 2868 3141 t
(.)2932 3143 w
(. .)1 56 1 2963 3144 t
(.)3027 3145 w
(.)3060 3146 w
(.)3091 3147 w
(.)3124 3148 w
(.)3156 3149 w
(.)3187 3150 w
(. .)1 54 1 3220 3151 t
(.)3284 3152 w
(.)3315 3153 w
(.)3348 3154 w
(.)3379 3155 w
(. .)1 55 1 3412 3156 t
(.)3475 3158 w
(. .)1 54 1 3508 3159 t
(.)3572 3160 w
(. .)1 56 1 3603 3162 t
(.)3667 3163 w
(.)3700 3164 w
(.)3732 3165 w
(.)3763 3166 w
(.)3796 3167 w
12 R f
(* 800,000)1 540 1 3808 3188 t
1821 3424 1792 3436 Dl
1888 3394 1859 3406 Dl
1914 3377 1887 3393 Dl
1965 3346 1938 3362 Dl
2015 3315 1988 3331 Dl
2044 3300 2016 3315 Dl
2100 3269 2072 3284 Dl
2157 3239 2129 3254 Dl
2214 3208 2186 3223 Dl
2271 3178 2243 3193 Dl
2303 3174 2272 3178 Dl
2363 3165 2332 3169 Dl
2422 3156 2391 3160 Dl
2483 3147 2452 3151 Dl
2543 3139 2512 3143 Dl
2603 3130 2572 3134 Dl
2663 3121 2632 3125 Dl
2723 3112 2692 3116 Dl
2783 3103 2752 3107 Dl
2815 3103 2784 3103 Dl
2877 3104 2846 3104 Dl
2939 3105 2908 3105 Dl
3001 3106 2970 3106 Dl
3062 3107 3031 3107 Dl
3124 3107 3093 3107 Dl
3186 3109 3155 3109 Dl
3248 3110 3217 3110 Dl
3311 3110 3280 3110 Dl
3373 3112 3342 3112 Dl
3435 3112 3404 3112 Dl
3497 3113 3466 3113 Dl
3559 3115 3528 3115 Dl
3620 3115 3589 3115 Dl
3682 3116 3651 3116 Dl
3744 3117 3713 3117 Dl
3806 3118 3775 3118 Dl
(* 1,000,000)1 570 1 3808 3123 t
2272 3177 1792 3436 Dl
2783 2987 2272 3178 Dl
3807 2981 2784 2986 Dl
(* 2,000,000)1 570 1 3808 3004 t
9 R f
(.)1780 3439 w
(.)1808 3426 w
(.)1838 3411 w
(.)1867 3398 w
(.)1896 3384 w
(.)1926 3370 w
(.)1955 3356 w
(.)1984 3342 w
(.)2013 3328 w
(.)2042 3314 w
(.)2071 3300 w
(.)2101 3286 w
(.)2130 3272 w
(.)2159 3258 w
(.)2188 3244 w
(.)2217 3230 w
(.)2246 3216 w
(.)2276 3202 w
(.)2304 3188 w
(.)2334 3174 w
(.)2363 3160 w
(.)2392 3146 w
(.)2421 3132 w
(.)2451 3118 w
(.)2479 3105 w
(.)2509 3090 w
(.)2538 3077 w
(.)2567 3062 w
(.)2597 3048 w
(.)2626 3035 w
(.)2655 3020 w
(.)2684 3007 w
(.)2713 2992 w
(.)2742 2979 w
(. .)1 23 1 2772 2965 t
(.)2803 2958 w
(.)2834 2953 w
(.)2865 2946 w
(.)2896 2940 w
(.)2927 2934 w
(.)2958 2928 w
(.)2988 2922 w
(.)3019 2916 w
(.)3051 2910 w
(.)3082 2904 w
(.)3113 2898 w
(.)3144 2892 w
(.)3175 2886 w
(.)3206 2879 w
(.)3237 2874 w
(.)3268 2867 w
(.)3299 2861 w
(.)3330 2855 w
(.)3361 2849 w
(.)3392 2843 w
(.)3423 2837 w
(.)3454 2830 w
(.)3485 2825 w
(.)3516 2819 w
(.)3547 2812 w
(.)3578 2807 w
(.)3609 2800 w
(.)3640 2794 w
(.)3671 2788 w
(.)3703 2782 w
(.)3734 2776 w
(.)3765 2770 w
(.)3796 2763 w
12 R f
(* 4,000,000)1 570 1 3808 2784 t
(* 8,000,000)1 570 1 3808 2698 t
12 B f
(FIG. 3. Speedups of PSS.)4 1279 1 2240 4160 t
cleartomark
showpage
saveobj restore
%%EndPage: 35 35
%%Page: 36 36
/saveobj save def
mark
36 pagesetup
12 R f
(- 36 -)2 260 1 2750 500 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 810 t
12 R f
(RDFAs)3011 950 w
12 S f
(_ ______________________________________________)1 2771 1 1784 970 t
12 R f
(Sizes)1347 1030 w
( 32PEs 64PEs)2 974( 16PEs)1 499(2PEs 4PEs 8PEs)2 1147 3 1875 1110 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1120 t
(_ _______________________________________________________)1 3351 1 1204 1140 t
12 R f
( -)1 372( 1.074)1 487( 1.030)1 468(100000 1.001 1.008 1.021)3 1710 4 1324 1270 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1290 t
12 R f
( -)1 372( 1.043)1 487( 1.032)1 468(200000 1.002 1.003 1.012)3 1710 4 1324 1430 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1450 t
12 R f
( -)1 372( 1.044)1 487( 1.017)1 468(400000 1.001 1.002 1.008)3 1710 4 1324 1590 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1610 t
12 R f
( 1.026 1.062)2 974( 1.017)1 468( 1.005)1 450(800000 - 1.002)2 1260 4 1324 1750 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1770 t
12 R f
( 1.021 1.047)2 974( 1.010)1 468( 1.004)1 450(1000000 - 1.001)2 1320 4 1264 1910 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1930 t
12 R f
( 1.016 1.045)2 974( 1.009)1 583( - -)2 900(2000000 -)1 755 4 1264 2070 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 2090 t
12 R f
( 1.026)1 487( 1.011)1 602( -)1 468( - -)2 900(4000000 -)1 755 5 1264 2230 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 2250 t
12 R f
( 1.017)1 602( -)1 487( -)1 468( - -)2 900(8000000 -)1 755 5 1264 2390 t
12 S f
( \347)1 -3351(_ _______________________________________________________)1 3351 2 1204 2410 t
(\347)1204 2370 w
(\347)1204 2250 w
(\347)1204 2130 w
(\347)1204 2010 w
(\347)1204 1890 w
(\347)1204 1770 w
(\347)1204 1650 w
(\347)1204 1530 w
(\347)1204 1410 w
(\347)1204 1290 w
(\347)1204 1170 w
(\347)1204 1050 w
(\347)1204 930 w
(\347)1764 2410 w
(\347)1764 2370 w
(\347)1764 2250 w
(\347)1764 2130 w
(\347)1764 2010 w
(\347)1764 1890 w
(\347)1764 1770 w
(\347)1764 1650 w
(\347)1764 1530 w
(\347)1764 1410 w
(\347)1764 1290 w
(\347)1764 1170 w
(\347)1764 1050 w
(\347)1764 930 w
(\347)1784 2410 w
(\347)1784 2370 w
(\347)1784 2250 w
(\347)1784 2130 w
(\347)1784 2010 w
(\347)1784 1890 w
(\347)1784 1770 w
(\347)1784 1650 w
(\347)1784 1530 w
(\347)1784 1410 w
(\347)1784 1290 w
(\347)1784 1170 w
(\347)1784 1050 w
(\347)1784 930 w
(\347)2224 2410 w
(\347)2224 2290 w
(\347)2224 2170 w
(\347)2224 2050 w
(\347)2224 1930 w
(\347)2224 1810 w
(\347)2224 1690 w
(\347)2224 1570 w
(\347)2224 1450 w
(\347)2224 1330 w
(\347)2224 1210 w
(\347)2224 1090 w
(\347)2674 2410 w
(\347)2674 2290 w
(\347)2674 2170 w
(\347)2674 2050 w
(\347)2674 1930 w
(\347)2674 1810 w
(\347)2674 1690 w
(\347)2674 1570 w
(\347)2674 1450 w
(\347)2674 1330 w
(\347)2674 1210 w
(\347)2674 1090 w
(\347)3124 2410 w
(\347)3124 2290 w
(\347)3124 2170 w
(\347)3124 2050 w
(\347)3124 1930 w
(\347)3124 1810 w
(\347)3124 1690 w
(\347)3124 1570 w
(\347)3124 1450 w
(\347)3124 1330 w
(\347)3124 1210 w
(\347)3124 1090 w
(\347)3611 2410 w
(\347)3611 2290 w
(\347)3611 2170 w
(\347)3611 2050 w
(\347)3611 1930 w
(\347)3611 1810 w
(\347)3611 1690 w
(\347)3611 1570 w
(\347)3611 1450 w
(\347)3611 1330 w
(\347)3611 1210 w
(\347)3611 1090 w
(\347)4098 2410 w
(\347)4098 2290 w
(\347)4098 2170 w
(\347)4098 2050 w
(\347)4098 1930 w
(\347)4098 1810 w
(\347)4098 1690 w
(\347)4098 1570 w
(\347)4098 1450 w
(\347)4098 1330 w
(\347)4098 1210 w
(\347)4098 1090 w
(\347)4555 2410 w
(\347)4555 2370 w
(\347)4555 2250 w
(\347)4555 2130 w
(\347)4555 2010 w
(\347)4555 1890 w
(\347)4555 1770 w
(\347)4555 1650 w
(\347)4555 1530 w
(\347)4555 1410 w
(\347)4555 1290 w
(\347)4555 1170 w
(\347)4555 1050 w
(\347)4555 930 w
12 B f
( of PSRS.)2 483( RDFAs)1 438(Table 3.)1 414 3 2212 2760 t
cleartomark
showpage
saveobj restore
%%EndPage: 36 36
%%Page: 37 37
/saveobj save def
mark
37 pagesetup
12 R f
(- 37 -)2 260 1 2750 500 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 810 t
12 R f
(RDFAs)3011 950 w
12 S f
(_ ______________________________________________)1 2771 1 1784 970 t
12 R f
(Sizes)1347 1030 w
( 32PEs 64PEs)2 974( 16PEs)1 499(2PEs 4PEs 8PEs)2 1147 3 1875 1110 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1120 t
(_ _______________________________________________________)1 3351 1 1204 1140 t
12 R f
( -)1 372( 2.861)1 487( 2.096)1 468(100000 1.342 1.373 2.029)3 1710 4 1324 1270 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1290 t
12 R f
( -)1 372( 2.515)1 487( 1.685)1 468(200000 1.339 1.349 1.722)3 1710 4 1324 1430 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1450 t
12 R f
( -)1 372( 2.425)1 487( 2.100)1 468(400000 1.351 1.403 1.485)3 1710 4 1324 1590 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1610 t
12 R f
( 2.150 2.001)2 974( 2.339)1 468( 1.441)1 450(800000 - 2.264)2 1260 4 1324 1750 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1770 t
12 R f
( 2.044 2.635)2 974( 1.996)1 468( 2.348)1 450(1000000 - 1.649)2 1320 4 1264 1910 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 1930 t
12 R f
( 2.104 2.447)2 974( 1.578)1 583( - -)2 900(2000000 -)1 755 4 1264 2070 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 2090 t
12 R f
( 2.670)1 487( 2.365)1 602( -)1 468( - -)2 900(4000000 -)1 755 5 1264 2230 t
12 S f
(_ _______________________________________________________)1 3351 1 1204 2250 t
12 R f
( 2.407)1 602( -)1 487( -)1 468( - -)2 900(8000000 -)1 755 5 1264 2390 t
12 S f
( \347)1 -3351(_ _______________________________________________________)1 3351 2 1204 2410 t
(\347)1204 2370 w
(\347)1204 2250 w
(\347)1204 2130 w
(\347)1204 2010 w
(\347)1204 1890 w
(\347)1204 1770 w
(\347)1204 1650 w
(\347)1204 1530 w
(\347)1204 1410 w
(\347)1204 1290 w
(\347)1204 1170 w
(\347)1204 1050 w
(\347)1204 930 w
(\347)1764 2410 w
(\347)1764 2370 w
(\347)1764 2250 w
(\347)1764 2130 w
(\347)1764 2010 w
(\347)1764 1890 w
(\347)1764 1770 w
(\347)1764 1650 w
(\347)1764 1530 w
(\347)1764 1410 w
(\347)1764 1290 w
(\347)1764 1170 w
(\347)1764 1050 w
(\347)1764 930 w
(\347)1784 2410 w
(\347)1784 2370 w
(\347)1784 2250 w
(\347)1784 2130 w
(\347)1784 2010 w
(\347)1784 1890 w
(\347)1784 1770 w
(\347)1784 1650 w
(\347)1784 1530 w
(\347)1784 1410 w
(\347)1784 1290 w
(\347)1784 1170 w
(\347)1784 1050 w
(\347)1784 930 w
(\347)2224 2410 w
(\347)2224 2290 w
(\347)2224 2170 w
(\347)2224 2050 w
(\347)2224 1930 w
(\347)2224 1810 w
(\347)2224 1690 w
(\347)2224 1570 w
(\347)2224 1450 w
(\347)2224 1330 w
(\347)2224 1210 w
(\347)2224 1090 w
(\347)2674 2410 w
(\347)2674 2290 w
(\347)2674 2170 w
(\347)2674 2050 w
(\347)2674 1930 w
(\347)2674 1810 w
(\347)2674 1690 w
(\347)2674 1570 w
(\347)2674 1450 w
(\347)2674 1330 w
(\347)2674 1210 w
(\347)2674 1090 w
(\347)3124 2410 w
(\347)3124 2290 w
(\347)3124 2170 w
(\347)3124 2050 w
(\347)3124 1930 w
(\347)3124 1810 w
(\347)3124 1690 w
(\347)3124 1570 w
(\347)3124 1450 w
(\347)3124 1330 w
(\347)3124 1210 w
(\347)3124 1090 w
(\347)3611 2410 w
(\347)3611 2290 w
(\347)3611 2170 w
(\347)3611 2050 w
(\347)3611 1930 w
(\347)3611 1810 w
(\347)3611 1690 w
(\347)3611 1570 w
(\347)3611 1450 w
(\347)3611 1330 w
(\347)3611 1210 w
(\347)3611 1090 w
(\347)4098 2410 w
(\347)4098 2290 w
(\347)4098 2170 w
(\347)4098 2050 w
(\347)4098 1930 w
(\347)4098 1810 w
(\347)4098 1690 w
(\347)4098 1570 w
(\347)4098 1450 w
(\347)4098 1330 w
(\347)4098 1210 w
(\347)4098 1090 w
(\347)4555 2410 w
(\347)4555 2370 w
(\347)4555 2250 w
(\347)4555 2130 w
(\347)4555 2010 w
(\347)4555 1890 w
(\347)4555 1770 w
(\347)4555 1650 w
(\347)4555 1530 w
(\347)4555 1410 w
(\347)4555 1290 w
(\347)4555 1170 w
(\347)4555 1050 w
(\347)4555 930 w
12 B f
( for PSS.)2 450( RDFAs)1 438(Table 4.)1 414 3 2229 2760 t
cleartomark
showpage
saveobj restore
%%EndPage: 37 37
%%Page: 38 38
/saveobj save def
mark
38 pagesetup
12 R f
(- 38 -)2 260 1 2750 500 t
12 I f
(Data gathering in phase 1:)4 1302 1 1440 860 t
12 B f
(for)1800 1140 w
12 I f
(j)1983 1140 w
12 S f
(=)2077 1140 w
12 R f
(log)2203 1140 w
12 I f
(p)2407 1140 w
12 R f
(, log)1 234 1 2477 1140 t
12 I f
(p)2761 1140 w
12 S f
(-)2881 1140 w
12 R f
(1 ,)1 100 1 3007 1140 t
12 I f
(.)3157 1140 w
12 R f
( 1)1 110(.. ,)1 100 2 3187 1140 t
12 B f
(do)3427 1140 w
12 R f
(All nodes numbered 0)3 1064 1 2160 1280 t
9 R f
(log)3231 1232 w
9 I f
(p)3383 1232 w
9 S f
(-)3473 1232 w
9 I f
(j)3576 1232 w
12 R f
(1)3621 1280 w
12 I f
(a)3691 1280 w
9 I f
(j)3766 1304 w
12 R f
(, where)1 352 1 3801 1280 t
12 I f
(a)4183 1280 w
9 I f
(j)4258 1304 w
12 R f
(is any)1 284 1 4323 1280 t
(\()2160 1420 w
12 I f
(j)2200 1420 w
12 S f
(-)2254 1420 w
12 R f
(1\)-bit binary number, send in parallel their respective data)8 2795 1 2340 1420 t
(accumulated from the previous steps to nodes 0)7 2287 1 2160 1560 t
9 R f
(log)4454 1512 w
9 I f
(p)4606 1512 w
9 S f
(-)4696 1512 w
9 I f
(j)4799 1512 w
9 S f
(+)4869 1512 w
9 R f
(1)4964 1512 w
12 I f
(a)5029 1560 w
9 I f
(j)5104 1584 w
12 R f
(.)5139 1560 w
12 I f
(Data broadcasting in phase 2:)4 1469 1 1440 1980 t
12 B f
(for)1800 2260 w
12 I f
(j)1983 2260 w
12 S f
(=)2077 2260 w
12 R f
( ,)1 40( 2)1 110(1 ,)1 100 3 2203 2260 t
12 I f
(.)2503 2260 w
12 R f
( log)1 204(.. ,)1 100 2 2533 2260 t
12 I f
(p)2887 2260 w
12 B f
(do)2977 2260 w
12 R f
(All nodes numbered 0)3 1064 1 2160 2400 t
9 R f
(log)3231 2352 w
9 I f
(p)3383 2352 w
9 S f
(-)3473 2352 w
9 I f
(j)3576 2352 w
9 S f
(+)3646 2352 w
9 R f
(1)3741 2352 w
12 I f
(a)3806 2400 w
9 I f
(j)3881 2424 w
12 R f
(, where)1 352 1 3916 2400 t
12 I f
(a)4298 2400 w
9 I f
(j)4373 2424 w
12 R f
(is any)1 284 1 4438 2400 t
(\()2160 2540 w
12 I f
(j)2200 2540 w
12 S f
(-)2254 2540 w
12 R f
(1\)-bit binary number, send in parallel the received)7 2410 1 2340 2540 t
12 I f
(p)4780 2540 w
12 S f
(-)4900 2540 w
12 R f
(1 pivots)1 385 1 5026 2540 t
(to nodes 0)2 494 1 2160 2680 t
9 R f
(log)2661 2632 w
9 I f
(p)2813 2632 w
9 S f
(-)2903 2632 w
9 I f
(j)3006 2632 w
12 R f
(1)3051 2680 w
12 I f
(a)3121 2680 w
9 I f
(j)3196 2704 w
12 R f
(.)3231 2680 w
12 I f
(Data exchange operations in phase 3:)5 1831 1 1440 3100 t
12 B f
(for)1800 3380 w
12 I f
(k)1983 3380 w
12 S f
(=)2096 3380 w
12 R f
( ,)1 40( 2)1 110(1 ,)1 100 3 2222 3380 t
12 I f
(.)2522 3380 w
12 R f
( log)1 204(.. ,)1 100 2 2552 3380 t
12 I f
(p)2906 3380 w
12 B f
(do)2996 3380 w
12 R f
(Each node)1 502 1 2160 3526 t
12 I f
(i)2692 3526 w
12 R f
(, such that \()3 561 1 2726 3526 t
12 I f
(i)3297 3526 w
12 R f
(\))3341 3526 w
9 I f
(k)3396 3550 w
12 R f
(= 1, exchanges with node)4 1223 1 3476 3526 t
12 I f
(i)4729 3526 w
12 S1 f
(_)4722 3415 w
9 I f
(k)4778 3466 w
12 R f
(all sublists)1 514 1 2160 3666 t
12 I f
(L)2704 3666 w
9 I f
(i)2786 3690 w
9 R f
(,)2818 3690 w
9 I f
(j)2856 3690 w
12 R f
(and)2921 3666 w
12 I f
(L)3124 3666 w
9 I f
(i)3206 3690 w
9 S1 f
(_)3203 3599 w
6 I f
(k)3241 3626 w
9 R f
(,)3281 3690 w
9 I f
(j)3349 3690 w
9 S1 f
(_)3346 3599 w
6 I f
(k)3384 3626 w
12 R f
(,)3427 3666 w
(for all 0)2 381 1 2160 3806 t
12 S f
(\243)2591 3806 w
12 I f
(j)2717 3806 w
12 S f
(\243)2801 3806 w
12 I f
(p)2917 3806 w
12 S f
(-)3037 3806 w
12 R f
(1 such that \()3 591 1 3163 3806 t
12 I f
(j)3784 3806 w
12 R f
(\))3828 3806 w
9 I f
(k)3883 3830 w
12 S f
(=)3993 3806 w
12 R f
(0.)4119 3806 w
12 B f
( on a Hypercube.)3 874( PSRS)1 353(FIG. 4.)1 364 3 2444 4226 t
cleartomark
showpage
saveobj restore
%%EndPage: 38 38
%%Page: 39 39
/saveobj save def
mark
39 pagesetup
12 R f
(- 39 -)2 260 1 2750 500 t
(Author biographies:)1 965 1 1440 860 t
(Hanmao Shi:)1 631 1 1440 1140 t
( his B.Sc. degree from the University of Science and)9 2561(Hanmao Shi received)2 1039 2 1440 1420 t
( Computer Science)2 932(Technology of China in 1988 and his M.Sc. degree in)9 2668 2 1440 1560 t
( Ph.D. candidate)2 799( he is a)3 343( Currently,)1 553(from the University of Alberta in 1990.)6 1905 4 1440 1700 t
( research interests)2 867( His)1 230( of Waterloo.)2 643(in Computer Science at the University)5 1860 4 1440 1840 t
( and)1 234(include parallel and distributed computing, database management,)6 3366 2 1440 1980 t
(artificial intelligence.)1 1031 1 1440 2120 t
(Jonathan Schaeffer:)1 950 1 1440 2540 t
( degree from the University of)5 1643(Jonathan Schaeffer received his B.Sc.)4 1957 2 1440 2820 t
( Com-)1 321(Toronto \(1979\), and M.Math \(1980\) and Ph.D. \(1986\) degrees in)9 3279 2 1440 2960 t
( he is an Associ-)4 802( Currently)1 523( University of Waterloo.)3 1181(puter Science from the)3 1094 4 1440 3100 t
( Department of Computing Science, University of)6 2586(ate Professor at the)3 1014 2 1440 3240 t
( include parallel and distributed computing)5 2104( research interests)2 873(Alberta. His)1 623 3 1440 3380 t
(and artificial intelligence.)2 1234 1 1440 3520 t
cleartomark
showpage
saveobj restore
%%EndPage: 39 39
%%Trailer
done
%%Pages: 39
%%DocumentFonts: Times-Bold Times-Italic Times-Roman Symbol Times-Roman
